图的一种特殊的（d，1）－全标号

张 焕，左连翠

（天津师范大学 数学科学学院，天津 300387）

图的一种特殊的（d，1）－全标号

张 焕，左连翠

（天津师范大学 数学科学学院，天津 300387）

设图G是有限的、无向的简单图.对于Δ（G）≥2d＋2的情况，给出了一种在［0，2Δ＋d－2］上d－好标号的方法，改进了相关文献的结果.

（d，1）－全标号；d－好标号；跨度；（d，1）－全数

1 引言及预备知识

在进行电频波分配时经常出现这种情况：需要将电频波分配给不同的传输站，每个传输站得到的电频波是一个整数.为了避免干扰，如果2个传输站距离较近，则它们接收的电频波的波段要有一定的间隔.为了解决这个问题，文献［1］定义了L（2，1）－标号.图G的L（2，1）－标号是一个整数集到图G的顶点的分配，满足任意2个相邻的顶点的标号之差至少为2，任意2个距离为2的顶点的标号互不相同.L（d，1）－标号［2］是L（2，1）－标号的一个自然推广.而（d，1）－全标号［3］是L（d，1）－标号的一种特殊推广，它由M.A.Whittlesey等首先提出.

2 主要结果

设图G是有限的、无向的简单图.令A是V（G）的一个子集，B＝V（G）－A，［A，B］是一个边集，并且［A，B］中任意边满足其2个端点分别在A，B中.称［A，B］为图G的一个割边.称图G的所有割边中边数最多的割为图G的最大割.令G（A）是A的导出子集，G（A）简记为.

引理1［4］令图G的最大度为2k＋1，则存在G的一个最大割［A，B］，满足Δ）≤k，Δ）≤k.

引理2［4］令图G的最大度为2k，则存在G的一个割［A，B］，满足Δ）≤k－1，Δ）≤k.

引理2中的割实际上也是最大割.

引理3［4］令图G是一个最大度为Δ的二部图，则G存在一个在［1，Δ］中的边着色c，使得边e的标号c（e）≥i当且仅当e与一个度至少为i的顶点相关联.

从引理3的证明可以看出，若G是一个二部图，则存在一个边着色c，使得边e的标号c（e）＝i当且仅当e与一个度至少为i的顶点相关联.当然，此时可以交换边的颜色，使得c（e）＝j当且仅当e与一个度至少为i的顶点相关联，其中i，j∈［0，Δ］.

引理4［4］令图G的最大度Δ≤k，则G在［0，2k＋d－1］中存在一个（d，1）－全标号，使得顶点v得到的标号在［0，d（v）］中，边的标号在［k＋d－1，2k＋d－1］中.

引理5［4］令图G的最大度Δ≤k，则G在［0，2k＋d－1］中存在一个（d，1）－全标号，使得边的标号在［0，k］中，顶点v得到的标号在［k＋d－1，k＋d－1＋d（v）］中.

文献［4］给出了当d＝2时，G在［0，2Δ＋d－2］中有一个d－好标号，下面设d≥3.

定理1 如果Δ（G）＝2k＋1，并且k≥d，则G在［0，2Δ＋d－2］中有一个d－好标号.

根据引理3，对割［A，B］用［2k＋d，4k＋d］进行标号，使得边e标2k＋d＋i当且仅当边e与一个在G（［A，B］）中度至少为2k＋1－i的顶点相关联.因为Δ（G）＝2k＋1，则e与一个在或中度至多为i的顶点相关联，其中i＝0，1，…，d－2.

对于［A，B］中的边（a，b）的标号，除了（a，b）标2k＋2d－2－s并且b标2k＋d－1－j之外，其余的标号均满足（d，1）－全标号的限制，其中，s＝0，1，…，d－2；j＝0，1，…，s.

这时，边（a，b）标2k＋d＋i当且仅当a在中不大于i，其中i＝0，1，…，d－2，则0≤l（a）≤i.

下面对不满足（d，1）－全标号限制的边进行重新标号.

对于已标2k＋d＋i′的边e，对e重新标k＋i′即可，其中i′＝1，2，…，d－2.对于标2k＋d的边e，当2d－2≤k时，2k－d＋1≥k＋d－1，即2kd＋1在E）的标号段中，这时对e重新标2kd＋1，因为a在中是孤立点，所以重新标号是满足（d，1）－全标号限制的；当d≤k＜2d－2时，如果边e与一个标2k＋m的顶点b相关联，则对边e重新标k＋m，其中m＝1，2，…，d－1，因为k≥d并且a在中是孤立点，所以这种重新标号也是满足（d，1）－全标号限制的.

其他边和顶点保持标号不变.

在这个（d，1）－全标号中，每个顶点的标号都在［0，2k＋d－1］中，所以这个标号是G在［0，4k＋d］中的d－好标号.

定理2 如果Δ（G）＝2k≥2d＋2，则G在［0，2Δ＋d－2］上有一个d－好标号.

根据引理3，对割［A，B］用［2k＋d－1，4k＋d－2］进行标号，使得边e标2k＋d－1＋i当且仅当边e与一个在G（［A，B］）中度至少为2k－i的顶点相关联.因为Δ（G）＝2k，则e与一个在或中度至多为i的顶点相关联，其中i＝0，1，…，d－2.

对于［A，B］中的边（a，b）的标号，除了a标2k＋j并且边（a，b）标2k＋d－1＋i，其中，j＝0，1，…，d－2，0≤i≤j（情况1），或者（a，b）标2k＋d－1并且b与中一个标2k＋d－1的边相关联（情况2）之外，其余的标号均满足（d，1）－全标号的限制.

下面对部分边和顶点重新着色.

情况1 由于k≥d，则（v）≥k＋j－d＋1≥i＋（k－d＋1）＞i.从而当（a，b）标2k＋d－1＋i时，b的标号不多于i.对于标2k＋d－1＋i′的边（a，b），对其重新标k＋i′，其中i′＝1，2，…，d－2.对于标2k＋d－1的边，如果k≥2d－1，则k＋d－1≤2k－d≤2k＋d－2，这时对边（a，b）重新标2k－d；否则，对边（a，b）重新标0，对b重新标k.这种重新标号是可以的，因为b在中是孤立点，并且0没有在的边标号中出现.

情况2 此时b在中不是孤立点，从而a在中是孤立点.如果l（b）≥d，则对边（a，b）重新标0.如果l（b）≤d－1并且k≥2d，则对边（a，b）重新标2d－1.这种标号是可以的，因为3d－1＝2（d＋1）＋d－3≤2k＋d－3，并且3d－1＝2d＋d－1≥（k＋1）＋d－1＝k＋d，所以3d－1∈［k＋d，2k＋d－3］.从而，［A，B］中至多有（4d－2）－（2k＋d－1）＋1＝3d－2k≤d－2条边不满足（d，1）－全标号的限制，可如情况1一样对这些边重新标号.

其他边和顶点保持标号不变.这样得到了一个顶点标号均在［0，2k＋d－2］中的（d，1）－全标号.

由定理1—2可以得到下面的推论.

推论 如果Δ（G）≥2d＋2，则G在［0，2Δ＋d－2］中有一个d－好标号.

［1］ Griggs J R，Yeh R K.Labeling graphs with a condition at distance two［J］.SIAM J Discrete Math，1992，5：586－595.

［2］ Chang G J，Ke W，Liu D D，et al.On（d，1）－labelings of graphs［J］.Discrete Math，2000，220：57－66.

［3］ Whittlesey M A，Georges J P，Mauro D W.On theλ－number ofQnand related graphs［J］.SIAM J Discrete Math，1995，8：499－506.

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

［5］ Lih K W，Liu D D，Wang W F.On（d，1）－total numbers of graphs［J］.Discrete Math，2009，309：3767－3773.

A special（d，1）－total labeling of graph

ZHANGHuan，ZUOLiancui
（College of Mathematical Science，Tianjin Normal University，Tianjin 300387，China）

Gis a limited and undirected simple graph.A total labeling method is given to prove that for any graphGwithΔ（G）≥2d＋2，there is ad－good labeling ofGin［0，2Δ＋d－2］.And the results of related literatures are improved.

（d，1）－total labeling；d－good labeling；span；（d，1）－total number

O157.5

A

1671－1114（2011）02－0020－03

2010－04－07

天津师范大学引进人才基金资助项目（5RL066）

张 焕（1986—），女，硕士研究生.

左连翠（1964—），女，教授，博士，主要从事图论与最优化方面的研究.

（责任编校 马新光）