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

刘秀丽

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

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

刘秀丽

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

研究了与频道分配有关的1种 （p，1）－全标号染色问题.（p，1）－全标号是从V（G）∪E（G）到集合｛0，1，…，k｝的1个映射，满足：①G的任2个相邻的顶点得到不同的整数；②G的任2个相邻的边得到不同的整数；③任1个点和与它相关联的边得到的整数至少相差p.通过在2个简单图之间叠加一系列匹配构造了几类有趣图，并根据所构造图的特征，利用穷染法得到了这些图的（2，1）－全标号数.

染色；（p，1）－全标号；（p，1）－全标号数；弱联图

0 引言

由于图的染色问题在现实中有着广泛应用，因而该问题受到众多学者的重视.近年来，研究者［1－3］又提出了许多新的染色问题，且这些染色问题在频率分配中得到了很好的应用，如泛宽度染色和L（p，1）－标号.特别地，Whittlesey等人在文献［4］中研究了G的剖分图的L（2，1）－标号，G的剖分图S1（G）是由图G在每条边上插入1个点所得到的图.S1（G）的L（p，1）－标号对应于G的（p，1）－全标号.

图G为简单的连通图，用V（G）和E（G）分别表示图G的顶点集和边集，对∀v∈V（G），用dG（v）表示顶点v在图G中的度，用Δ（G）表示图G中顶点的最大度.本文所讨论的图均为简单有限图.

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

当p＝1时，图G的（p，1）－全标号对应于图G的全染色，因此图的（p，1）－全标号也是对图的全染色的一种推广.本文主要讨论几类特殊图的（2，1）－全标号.

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

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

引理3［5］若G是正则的，则λTp（G）≥Δ＋p.

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

1 主要结果及证明

设G和G′均为简单连通图，其顶点集分别为V（G）＝ ｛u1，u2，…，un｝，V（G′）＝ ｛v1，v2，…，vn｝.在G和G′之间叠加匹配uivi，uivi＋1，uivi＋2，…，uivi＋m，…，uivi＋（n－1），其中i＝1，2，…，n；m＝0，1，2，…，n－1；当i＋m＞n时，i＋m为modn意义下的加法.这样得到一系列新图称为图G和G′的弱联图.显然，G（n）n，n＝G∨G′.

定理1 设V1＝ ｛u1，u2，…，un｝，V2＝ ｛v1，v2，…，vn｝，在两部之间叠加上述匹配可得到一系列正则二部图Gn（1，n），Gn（2，n），…，Gn（m，n＋1），…，Gn（n，n）＝Kn，n，则有λ2T（Gn（m，n＋1））＝m＋3，其中m＝0，1，2，…，n－1.

证明 由图Gn（m，n＋1）的构造知，Δ（Gn（m，n＋1））＝m＋1，并且图Gn（m，n＋1）为（m＋1）－正则图.由引理3有，

下证λ2T（Gn（m，n＋1））≤m＋3.构造1个映射f∶V（Gn（m，n＋1））∪E（Gn（m，n＋1））→ ｛0，1，2，…，m＋3｝.f（ui）＝m＋2，f（vi）＝m＋3，i＝1，2，…，n；f（uivi＋j）＝j，i＝1，2，…，n，j＝0，1，2，…，m，当i＋j＞n时，i＋j为mod n意义下的加法.易证映射f是Gn（m，n＋1）的1个正常的（2，1）－全标号，所以λ2T（Gn（m，n＋1））≤m＋3.

综上，有λ2T（Gn（m，n＋1））＝m＋3，其中m＝0，1，2，…，n－1.

定理2 设Pn和P′n为2个阶均为n的路，在Pn和P′n之间叠加上述匹配得到一系列图Pn（1，n），Pn（2，n），…，Pn（m，n＋1），…，Pn（n，n），则有λ2T（Pn（m，n＋1））＝m＋5，其中m＝0，1，2，…，n－1，n≥4.

证明 不妨设V（Pn）＝ ｛u1，u2，…，un｝，V（P′n）＝ ｛v1，v2，…，vn｝.由图Pn（m，n＋1）的构造知，Δ（Pn（m，n＋1））＝m＋1＋2＝m＋3.由引理1得λ2T（Pn（m，n＋1））≥Δ＋2－1＝m＋4.

首先证明λ2T（Pn（m，n＋1））＝m＋4不成立，即标号集｛0，1，2，…，m＋4｝无法完成对图Pn（m，n＋1）的正常的（2，1）－全标号.运用反证法.假设存在1个映射f∶V（Pn（m，n＋1））∪E（Pn（m，n＋1））→ ｛0，1，2，…，m＋4｝是图Pn（m，n＋1）的1个正常的（2，1）－全标号，由引理2知，Pn（m，n＋1）的最大度点只能标0或m＋4.由图Pn（m，n＋1）的结构知，当n≥4时，最大度点生成的子图中包含三角形，而三角形的顶点色数为3，所以0和m＋4无法完成对最大度点的全标号，矛盾.所以λ2T（Pn（m，n＋1））≥m＋5.

再证λ2T（Pn（m，n＋1））≤m＋5.构造1个映射f∶V（Pn（m，n＋1））∪E（Pn（m，n＋1））→ ｛0，1，2，…，m＋5｝.用0，1循环标点u1，u2，…，un；用4，3循环标点v1，v2，…，vn；用3，4循环标边u1u2，u2u3，…，un－1un；用0，1循环标边v1v2，v2v3，…，vn－1vn；用2，5循环标边uivi（i＝1，2，…，n）；用 m＋5标边uivi＋m（i＝1，2，…，n；m＝1，2，…，n－1；当i＋m＞n时，i＋m为mod n意义下的加法）.易证映射f是Pn（m，n＋1）的1个正常的（2，1）－全标号.所以λ2T（Pn（m，n＋1））≤m＋5.

综上，有λ2T（Pn（m，n＋1））＝m＋5，其中m＝0，1，2，…，n－1，n≥4.

定理3 设Cn和C′n为2个阶均为n（n≥3）的圈，在Cn和C′n之间叠加上述匹配得到一系列正则图Cn（1，n），Cn（2，n），…，Cn（m，n＋1），…，Cn（n，n），则有：① 当n为偶数时，有λ2T（Cn（m，n＋1））＝m＋5，其中m＝0，1，2，…，n－1；② 当n为奇数时，有m＋5≤λ2T（Cn（m，n＋1））≤m＋6，其中m＝0，1，2，…，n－1.

证明 不 妨 设V（Cn）＝ ｛u1，u2，…，un｝，V（C′n）＝ ｛v1，v2，…，vn｝.由 图Cn（m，n＋1）的 构 造 知，.又因为Cn为2－正则图，所以Cn（m，n＋1）为（m＋3）－正则图，由引理3得

1）当n为偶数时.构造1个映射f∶V（Cn（m，n＋1））∪E（Cn（m，n＋1））→ ｛0，1，2，…，m＋5｝.用0，1循环标点u1，u2，…，un；用4，3循环标点v1，v2，…，vn；用3，4循环标边u1u2，u2u3，…，un－1un，unu1；用0，1循环标边v1v2，v2v3，…，vn－1vn，vnv1；用2，5循环标边uivi（i＝1，2，…，n）；用m＋5标边uivi＋m（i＝1，2，…，n；m ＝1，2，…，n－1；当i＋m＞n时，i＋m为mod n意义下的加法）.易证映射f是Cn（m，n＋1）的1个正常的（2，1）－全标号.所以λ2T（Cn（m，n＋1））≤m＋5.综上，当n为偶数时，有λ2T（Cn（m，n＋1））＝m＋5，其中m＝0，1，2，…，n－1.

2）当n为奇数时.构造1个映射f∶V（Cn（m，n＋1））∪E（Cn（m，n＋1））→ ｛0，1，2，…，m＋6｝.用0，1循环标点u1，u2，…，un－1，用2标点un；用4，3循环标点v1，v2，…，vn－1，用5标点vn；用3，4循环标边u1u2，u2u3，…，un－1un，用5标边unu1；用0，1循环标边v1v2，v2v3，…，vn－1vn，用2标边vnv1；用6，5，2，5循环标边uivi（i＝1，2，…，n－1），用0标边unvn；用m＋6标边uivi＋m（i＝1，2，…，n；m＝1，2，…，n－1；当i＋m ＞n时，i＋m为mod n意义下的加法）.易证映射f是Cn（m，n＋1）的1个正常的（2，1）－全标号.所以λ2T（Cn（m，n＋1））≤m＋6.综上，当n为奇数时，有m＋5≤λ2T（Cn（m，n＋1））≤m＋6，其中m＝0，1，2，…，n－1.

注：显然，当m＝0时，即为图Cn（1，n），称之为双圈［9］.

在本文的写作过程中，得到山东师范大学数学科学院的孙磊老师和高敬振老师的帮助，谨致谢意.

［1］Griggs J R，Yeh R K.Labelling graphs with a condition at distance two［J］.SIAMJ Discrete Math，1992，5（4）：586－595.

［2］Georges J P，Mauro D W，Stein MI.Labelling products of complete graphs with a condition at distance two［J］.SIAMJ Discrete Math，2001，14（1）：28－35.

［3］Georges J P，Mauro D W，Whittles MA.Relating path covering to vertex labellings with a condition at distance two［J］.Discrete Math，1994，135（1－3）：103－111.

［4］Whittles MA，Georges J P，Mauro D W.On theλ－number ofQnand related graphs［J］.SIAMJ Discrete Math，1995，8（4）：499－506.

［5］Havet F，Yu ML.（p，1）－total labelling of graphs［J］.Discrete Math，2008，308（4）：496－513.

［6］Chen Dong，Wang Wei－fan.（2，1）－Total labelling of outer planar graphs［J］.Discrete Applied Mathematics，2007，155（18）：2585－2593.

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

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

［9］孙磊，孙艳丽，董海燕.几类特殊图的邻点可区别的全染色［J］.西南师范大学学报：自然科学版，2006，31（4）：1－4.

The（2，1）－total labelling of some special graphs

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

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

istinct integers；②any two adjacent edges ofG

istinct integers；and③ a vertex and its incident edge receive integers that differ by at leastpin absolute value.Some special graphs are constructed by superimposing matchs between two simple graphs，and the（2，1）－total numbers of these graphs are given by the eternal coloring according to their feature.

coloring；（p，1）－total labelling；（p，1）－total number；weak join of two graphs

O157.5

A

1004－4353（2012）01－0038－03

2011－11－13

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