两类特殊图的（2 ，1）－全标号

刘秀丽

（菏泽学院 数学系，山东 菏泽274015）

两类特殊图的（2 ，1）－全标号

刘秀丽

（菏泽学院 数学系，山东 菏泽274015）

研究了与频道分配有关的一种染色问题——（p，1）－全标号.（p，1）－全标号是从V（G）∪E（G）到集合｛0，1，…，k｝的1个映射，满足：①G的任2个相邻的顶点得到不同的整数；②G的任2个相邻的边得到不同的整数；③ 任1个点和与它相关联的边得到的整数至少相差p.称最小的数k为图G的（p，1）－全标号数.根据所构造图的特征，利用穷染法得到了这些图的（2，1）－全标号数.

（p，1）－全标号；（p，1）－全标号数；Pkn图；Cn·Fm图

在频率分配问题中，会出现需要给中转站分配频率波段（每个中转站得到对应于1个整数的频率波段）的情况.为了避免干扰，如果2个站点离得非常近，那么它们的频率之差至少要相差2，而且如果2个站点离得近（不是非常近），那么它们得到的频率不同.受到这个问题的启发，Griggs和Yeh［1］引入了L（2，1）－标号，它的自然推广就是图G的L（p，1）－标号.关于这个标号已有作者对其进行了研究［2］，特别地，Whittlesey等在文献［3］中研究了G的剖分图S1（G）的L（2，1）－标号，S1（G）的L（p，1）－标号对应于G的（p，1）－全标号.

1 预备知识

定义1［4］设p是1个非负整数，图G的1个k－（p，1）－全标号是1个映射f∶V（G）∪E（G）→｛k｝，使得：①G的任2个相邻的顶点u和v，有0，1，…，②G的任2条相邻的边e和e′，有③G的任2个相关联的点v和边e，有全标号的跨度是指2个标号差的最大值，图G的（p，1）－全标号的最小跨度叫（p，1）－全标号数，记作λTp（G）.

当p＝1时，图G的（p1－全标号对应于图G的全染色，这种情况也被广泛研究，因此，图的（p，1）－全标号不仅与图的距离2标号问题密切相关，而且也是对图的全染色的一种推广.本文将主要讨论p＝2时即图G的（2，1）－全标号.

定义2［5］在含有n个顶点的路Pn上，当且仅当2点的距离（模）为k时加1条边，所得到的图称为Pkn图.

定义3［6］Fm表示阶为m＋1的扇，当n个扇Fm的扇心连成圈Cn时，用Cn·Fm表示.设V（Cn）＝｛v1，v2，…，vn｝，则

引理1［4］对任意图G，有λpT（G）≥Δ＋p－1.

引理2［7］若图G满足λ2T（G）＝Δ（G）＋1，映射f表示图G的1个标号集是｛0，1，2，…，Δ（G）＋1｝的（2，1）－全标号，那么对图G的每个最大度点v，有f（v）＝0或f（v）＝Δ（G）＋1.

文中未加说明的记号和术语参见文献［8］和［9］.

2 主要结果及证明

下面给出部分Pkn图的（2，1）－全标号.

定理1 对图Pkn，有λT2（Pkn）＝6，k＞1且k不能被12整除，n≥3k＋2.

证明 由图Pkn的定义易知，Δ（Pkn）＝4，由引理1有λT2（Pkn）≥Δ＋2－1＝5.首先证明λT2（Pkn）＝5不成立，即标号集｛0，1，2，3，4，5｝无法完成对图Pkn的正常的（2，1）－全标号.反证法.假设存在1个映射是图Pkn的1个正常的（2，1）－全标号.由引理2知，图Pkn的最大度点只能标0或5.不妨设V（Pn）＝ ｛v1，v2，…，vn｝.若n≥3k＋2，则存在1个最大度点vi至少与3个最 大度点vj，vm，vl相连.由（2，1）－全标号的定义知，与0和5相差2的只有2和3这2个数，无法完成对vivj，vivm，vivl这3条边的标号，矛盾，所以λT2（Pkn）≥6.

1）k≡0（mod 2）.1′2

2′但3不能整除k，即k＝4，8，16，20，28，32，40….①k＝4（3m－2），m＝1，2，3，…，即k＝4，16，28，40，….用0，4，6循环标点vi（i＝1，2，…，n）；用6，0，4循环标边vivi＋1（i＝1，2，…，n－1）；用2，1，3循环标边vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡1（mod 3））；用1，3，2循环标边vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡2（mod3））；用3，2，1循环标边vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡0（mod 3））.易证映射f是图Pkn的1个正常的（2，1）－全标号，所以λT2（Pkn）≤6.②k＝4（3m－1），m＝1，2，3，…，即k＝8，20，32，44，….用0，4，6循环标点vi（i＝1，2，…，n）；用6，0，4循环标边vivi＋1（i＝1，2，…，n－1）；用3，1，2循环标边vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡1（mod 3））；用2，3，1循环标边vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡2（mod 3））；用1，2，3循环标边vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡0（mod 3））.易证映射f是图Pkn的1个正常的（2，1）－全标号，所以λT2（Pkn）≤6.

2）k≡1（mod 2）.用0，1循环标点vi（i＝1，2，…，n）；用3，4循环标边vivi＋1（i＝1，2，…，n－1）；用5，6循环标边vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k）.易证映射f是图Pkn的1个正常的（2，1）－全标号，所以λT2（Pkn）≤6．

综上，有λT2（Pkn）＝6，k＞1，n≥3k＋2．

证明 1）n≡0（mod 2）．① 当m＝1时，由图Cn·Fm的定义易知，Δ（Cn·Fm）＝3．所以由引理1，有λT2（Cn·Fm）≥Δ＋2－1＝4．首先证明λT2（Cn·Fm）＝4不成立，即标号集｛0，1，2，3，4｝无法完成对图Cn·Fm的正常的（2，1）－全标号．事实上，假设存在1个映射是图Cn·Fm的1个正常的（2，1）－全标号．由引理2知，图Cn·Fm的最大度点vi（i＝1，2，…，n）只能标0或4，即＝0或若则4（i＋1为mod n意义下的加法），与0和4相差2的只有2这1个数．由（2，1）－全标号的定义知，无法完成对vi－1vi和vivi＋1这2条边的标号，矛盾．若）＝4，同理可得出矛盾，所以

再证λ2（Cn·Fm）≤5．构造1个映射用0，5循环标点v1，v2，…，vn；用2，3循环标边v1v2，v2v3，…，vn－1vn，vnv1；用2标点ui1（i＝1，2，…，n）．若0，则令若，则令易证映射f是图Cn·Fm的1个正常的（2，1）－全标号，所以λT2（Cn·Fm）≤5．综上，有λT2（Cn·Fm）＝5．

② 当m ≥2时，由图Cn·Fm的定义易知，Δ（Cn·Fm）＝m＋2．所以由引理1有，λT2（Cn·Fm）≥Δ＋2－1＝m＋3．下证λT2（Cn·Fm）≤m＋3．构造1个映射．用0，m＋3循环标点v1，v2，…，vn；用2，3循环标边v1v2，v2v3，…，vn－1vn，vnv1．若则用4，5，6，…，m＋3依次标边viui1，viui2，…，viuim；用2，3，4，…，m＋1依次标点ui1，ui2，…，uim；用0，1循环标边uijuij＋1（j＝1，2，…，m－1；i＝1，2，…，n）．若f （vi）＝m＋3，则用0，1，4，5，6，…，m＋1依次标边viui1，viui2，…，viuim；用2，3循环标点ui1，ui2，…，uim；用m＋3，m＋2循环标边uijuij＋1（j＝1，2，…，m－1；i＝1，2，…，n）．易证映射f 是图Cn·Fm的1个正常的（2，1）－全标号，所以λ2T（Cn·Fm）≤m＋3．综上，有λ2T（Cn·Fm）＝m＋3．

2）n≡1（mod 2）① 当m＝1时，由图Cn·Fm的定义易知，Δ（Cn·Fm）＝3．所以由引理1有，λ2T（Cn·Fm）≥Δ＋2－1＝4．首先证明λ2T（Cn·Fm）＝4不成立，即标号集｛0，1，2，3，4｝无法完成对图Cn·Fm的正常的（2，1）－全标号．事实上，假设存在1个映射是图Cn·Fm的1个正常的（2，1）－全标号．由引理2知，图Cn·Fm的最大度点vi（i＝1，2，…，n）只能标0或4，即或．显然无法完成对奇数个点的正常（2，1）－全标号，所以λT2（Cn·Fm）＝4不成立，因此

再证λT2（Cn·Fm）≤5．构造1个映射用0，5循环标点v1，v2，…，vn－1；用1标点vn；用2，3循环标边v1v2，v2v3，…，vn－1vn；用4标边vnv1；用2标点ui1（i＝1，2，…，n）．若或1，则令若，则令易证映射f是 图Cn·Fm的1个正常的（2，1）－全标号，所以λT2（Cn·Fm）≤5．综上，有λT2（Cn·Fm）＝5．② 当m≥2时，由图Cn·Fm的定义易知．所以由引理1，有m＋3．首先证明λT2（Cn·Fm）＝m＋3不成立，即标号集｛0，1，2，3，…，m＋3｝无法完成对图Cn·Fm的正常 的 （2，1）－全 标 号． 事 实 上， 假 设 存 在 1 个 映 射是图Cn·Fm的1个正常的（2，1）－全标号．由引理2知，图Cn·Fm的最大度点vi（i＝1，2，…，n）只能标0或m＋3，即或．显然这2个数无法完成对奇数个点的正常（2，1）－全标号，所以λT2（Cn·Fm）＝m＋3不成立，因此λT2（Cn·Fm）≥m＋4．

下证λT2（Cn·Fm）≤m＋4．构造1个映射用0，m＋3循环标点v1，v2，…，vn－1；用1标点vn；用2，3循环标边v1v2，v2v3，…，vn－1vn，用4标边vnv1；若则用4，5，6，…，m＋3依次标边viui1，viui2，…，viuim；用2，3，4，…，m＋1依次标点ui1，ui2，…，uim；用0，1循环标边uijuij＋1（j＝1，2，…，m－1；i＝2，3，…，n－1）．若，则用0，1，4，5，6，…，m＋1依次标边viui1，viui2，…，viuim；用2，3循环标点ui1，ui2，…，uim；用m＋3，m＋2循环标边uijuij＋1（j＝1，2，…，m－1；i＝2，3，…，n－1）．

用2，3循环标点u11，u12，…，u1m；用5，6，7，…，m＋4依次标边v1u11，v1u12，…，v1u1m；用0，5循环标边u1ju1j＋1（j＝1，2，…，m－1）；用2，3，4，5，…，m＋1依次标点un1，un2，…，unm；用5，6，7，8，…，m＋4依次标边vnun1，vnun2，…，vnunm；用0，1循环标边unjunj＋1（j＝1，2，…，m－1）．易证映射f是图Cn·Fm的1个正常的（2，1）－全标号，所以λT2（Cn·Fm）≤m＋4．综上，有λT2（Cn·Fm）＝m＋4，且当n≡0（mod 2）时，有当n≡1（mod 2）时，有

［1］ Griggs J R，Yeh R K．Labeling Graphs with a Condition at Distance Two［J］．SIAMJ Discrete Math，1992，5（4）：586－595．

［2］ Chang G J，ke W T，Yeh R K，et al．OnL（d，1）－labeling of Graphs［J］．Discrete Math，2000，220：57－66．

［3］ Whittles MA，Georges J P，Mauro D W．On theλ－Number ofQnand Related Graphs［J］．SIAMJ Discrete Math，1995，8（4）：499－506．

［4］ Havet F，Yu ML．（p，1）－total Labeling of Graphs［J］．Discrete Math，2008，308（4）：496－513．

［5］ 马生全，李敬文，等．Pkn（k≡2（mod 3））的邻点可区别的强全染色［J］．经济数学，2003，20（4）：77－80．

［6］ 李敬文，刘君，张忠辅，等．Cn·Fm的邻点可区别的边色数［J］．兰州交通大学学报，2004，23（4）：128－130．

［7］ Chen Dong，Wang Wei－fan．（2，1）－total Labeling of Outer Planar Graphs［J］．Discrete Applied Mathematics，2007，155（18）：2585－2593．

［8］ Bollobas B．Modern Graph Theory［M］．Ne wYork：Springer－Verlag，1998：145－177．

［9］ Bondy J A，Murty U S R．Graph Theory with Applications［M］．London：Macmillan Press Ltd，1976：123－196．

The（2，1）－total Labeling of Two Special Graphs

LIU Xiu－li
（DepartmentofMathematics，HezeUniversity，Heze274015，China）

We studied（p，1）－totallabeling of a graphsG，which related to frequency assignment problem of coloring problem. （p，1）－total labeling is an assignment from the set V（G） ∪E（G） to the integer ｛0，1，…，k｝，such that：①any two adjacent vertices ofG

istinct integers；②any two adjacent edges ofG

istinctintegers；③a vertex and its incident edge receive integers that differ by at leastpin absolutevalue.The minimal number ofkis called the（p，1）－total number ofG.The（2，1）－total numbers of these graphs were given by the eternal coloring according to their feature.

（p，1）－totallabeling；（p，1）－total number；Pkngraph；Cn·Fmgraph

O157.5

A

1004－4353（2011）03－0230－04

2011 -04 -12

刘秀丽（1977—），女，讲师，研究方向为图论与组合优化.