东南大学学报（英文版）
東南大學學報（英文版）
동남대학학보（영문판）
JOURNAL OF SOUTHEAST UNIVERSITY
2005年
1期
115-118
,共4页
regular tiling%频道分配问题%点着色%L(d,1)-标号着色%L(2,1)-标号着色
regular tiling%頻道分配問題%點著色%L(d,1)-標號著色%L(2,1)-標號著色
regular tiling%빈도분배문제%점착색%L(d,1)-표호착색%L(2,1)-표호착색
regular tiling%frequency assignment problem%vertex labeling%L(d,1)-labeling%L(2,1)-labeling
L(d,1)-标号着色是L(2,1)-标号着色的推广,这一图的点着色问题来自于无线电波中的频道分配问题,要求图中相邻顶点所着的颜色相差至少d,距离为2的顶点所着颜色必须不相同.由于d＝0,1,2时regular tilings的L(d,1)-标号着色数已由Calamoneri和Petreschi给出,本文研究d≥3时所有3种regular tilings的L(d,1)-标号着色,给出它们的L(d,1)-标号着色数.结合Calamoneri和Petreschi的结果,对所有非负整数d,regular tilings 的L(d,1)-标号着色数已完全确定.
L(d,1)-標號著色是L(2,1)-標號著色的推廣,這一圖的點著色問題來自于無線電波中的頻道分配問題,要求圖中相鄰頂點所著的顏色相差至少d,距離為2的頂點所著顏色必鬚不相同.由于d＝0,1,2時regular tilings的L(d,1)-標號著色數已由Calamoneri和Petreschi給齣,本文研究d≥3時所有3種regular tilings的L(d,1)-標號著色,給齣它們的L(d,1)-標號著色數.結閤Calamoneri和Petreschi的結果,對所有非負整數d,regular tilings 的L(d,1)-標號著色數已完全確定.
L(d,1)-표호착색시L(2,1)-표호착색적추엄,저일도적점착색문제래자우무선전파중적빈도분배문제,요구도중상린정점소착적안색상차지소d,거리위2적정점소착안색필수불상동.유우d＝0,1,2시regular tilings적L(d,1)-표호착색수이유Calamoneri화Petreschi급출,본문연구d≥3시소유3충regular tilings적L(d,1)-표호착색,급출타문적L(d,1)-표호착색수.결합Calamoneri화Petreschi적결과,대소유비부정수d,regular tilings 적L(d,1)-표호착색수이완전학정.
L(d,1)-labeling is a kind of graph coloring problem from frequency assignment in radio networks,in which adjacent nodes must receive colors that are at least d apart while nodes at distance two from each other must receive different colors.We focus on L(d,1)-labeling of regular tilings for d≥3 since the cases d＝0,1 or 2 have been researched by Calamoneri and Petreschi.For all three kinds of regular tilings,we give their L(d,1)-labeling numbers for any integer d≥3.Therefore,combined with the results given by Calamoneri and Petreschi,the L(d,1)-labeling numbers of regular tilings for any nonnegative integer d may be determined completely.
