几乎完全二部图的距离标号边跨度

张小玲

（泉州师范学院数学与计算机科学学院，福建泉州362000）

几乎完全二部图的距离标号边跨度

张小玲

（泉州师范学院数学与计算机科学学院，福建泉州362000）

研究几乎完全二部图（即完全二部图Kn，n去掉一个1-因子）的L（1，1）和L（2，1）边跨度.基于图的L（1，1）跨度确定了L（1，1）边跨度.通过给出具体标号得到图的L（2，1）边跨度的上界，进而利用反证法确定了L（2，1）边跨度的确切值.

几乎完全二部图；1-因子；距离标号；边跨度

1 引言及主要结果

图的距离标号问题源于无线电网络中的频率分配问题，1992年，Griggs等[1]将其抽象为图的距离标号问题，并考虑了更一般的L（j，k）-标号.给定正整数j和k（j≥k），图G的L（j，k）-标号为定义在V（G）上值域为非负整数的函数f，满足：对于G中的任意2点u和v，若uv∈E（G），则|f（u）-f（v）|≥j；若u和v距离为2，即d（u，v）=2，则|f（u）-f（v）|≥k.

L（j，k）-标号问题最初的优化目标是确定图G的L（j，k）跨度，即所有标号中最大标号的最小值，记为λj，k（G）.Bodlaender等[2]证明了确定一般图的L（j，k）跨度是NP-完全的，甚至二部图，乃至平面二部图的L（2，1）跨度问题都是NP-完全的.因而，大量的工作致力于确定各种特殊图的L（j，k）跨度[3-6]，尤其是L（2，1）跨度[7-8].在一些特殊需要的驱动下，除了图的跨度之外，还有许多关于L（j，k）-标号的指标被提出来.如，圆距离标号下的跨度[9]、实数意义下的距离标号跨度[10]、平衡距离标号下的跨度[11]、图的距离标号边跨度[12]等.

本研究考虑图的距离标号边跨度.假设图G的所有L（j，k）-标号中的最小值均为0.给定图G的一个L（j，k）-标号f，f的边跨度定义为

图G的L（j，k）边跨度βj，k（G）定义为G所有L（j，k）-标号中边跨度的最小值.特别地，图G的L（2，1）边跨度记为β（G）.与图的跨度相比，图的边跨度是一个局部优化的目标函数，因此不会超过图的跨度，即βj，k（G）≤λj，k（G）.图的边跨度概念最早由Yeh[12]提出，同时确定了圈、树、完全多部图、三角格图和四角格图的L（2，1）边跨度.文献[13]研究了一些特殊图类的L（d，1）边跨度.此后，树及2条路的乘积图的L（j，k）边跨度[14]、圈及完全多部图的实数 L（j，k）边跨度[15]也被确定.区别于以往求边跨度的方法，文献[16-18]借助整数流和Tension理论研究了平面图[16]、非平面图[17]和有向图[18]的边跨度.

图G的1-因子是指每个点仅关联1条边的G的生成子图.本研究记M为完全二部图Kn，n的一个1-因子.设V′和E′分别为V（G）和E（G）的非空子集，定义G-V′为G去掉V′以及V′中的顶点所关联的边之后的

子图，G-E′为G去掉E′之后的子图.完全二部图Kn，n去掉一个1-因子M之后得到的图，即Kn，n-M，称为几乎完全二部图.本研究考虑Kn，n-M的L（1，1）及L（2，1）边跨度，得到如下结果：

定理1 设n≥5，则β1，1（Kn，n-M）=n-1.

定理2 设n≥8，则β（Kn，n-M）=「3n/2-1.

2 主要结果的证明

引理[19]λ1，1（Kn，n-M）=n-1且λ2，1（Kn，n-M）= 2n-2.

定理1的证明 首先，由引理知，β1，1（Kn，n-M）≤λ1，1（Kn，n-M）=n-1.

另一方面，假设f是Kn，n-M的一个L（1，1）-标号.不失一般性，令f（v）=0.由于|N（v）|=n-1且N（v）∪{v}中的顶点标号两两不同，所以f（N（v））的最大标号不小于n-1.因此，β1，1（Kn，n-M）≥n-1.故有β1，1（Kn，n-M）=n-1.证毕.

对于整数a和b（a≤b），记[a，b]={a，a+1，…，b-1，b}.

定理2的证明 令G=（A，B），其中A={x1，x2，…，xn}，B={y1，y2，…，yn}，且M={xiyi|i=1，2，…，n}，G如图1所示.现给出G的标号：

图1 几乎完全二部图GFig.1 Almost complete bipartite graph G

下面考虑β（G）的下界.设f是G的任意一个L（2，1）-标号，并假定f（u）=0，

由引理易知p≥λ2，1（G）=2n-2.下证β（G，f）≥「3n/2-1.

若uv∈E（G），则由n≥8知β（G，f）=p≥λ2，1（G）= 2n-2≥「3n/2-1.

若uv∉E（G），分2种情形讨论.

情形1 u和v在不同部.不失一般性，设u∈A且v∈B.

令G1=G-{u，v}，f（w），f（v1）=f|V(G1）也是G1的L（2，1）-标号.

如果u1∈A或v1∈B，则G1同构于完全二部图Kn-1，n-1去掉一个1-因子，且n≥8，故有

如果u1∈B且v1∈A，此时，若u1v1∈E（G1），则有

β（G，f）≥f（v1）-f（u1）≥λ2，1（G1）=2n-4≥「3n/2-1若u1v1∉E（G1），令G2=G-{u，v，u1，v1}.f|V(G2)也是G2的L（2，1）-标号且λ2，1（G2）=2n-6（由于G2同构于Kn-2，n-2去掉一个1-因子）.令如果u2∈A，则

如果u2∈B，则

情形2 u和v在同一部.不失一般性，设u、v∈A，则B中顶点的标号都不同于u和v的标号，否则

β（G,f）=p≥λ2，1（G）=2n-2≥「3n/2-1

设uu′、vv′∈M，其中u′、v′∈B.令z和y分别为f在B{u′，v′}中的最大标号和最小标号.使用反证法.假设β（G，f）≤「3n/2-2，那么p-y≤「3n/2-2且z≤「3n/2-2.故有

另一方面，由于B{u′，v′}中的顶点的标号两两不同，所以z-y≥n-3.下面分3种子情形讨论.

情形2.1 z-y=n-1.

设ai为L中的标号在f下出现i的个数，即ai= |{k：lk=i}|，其中i=0，1，2.ai满足a0+a1+a2=2n-1和2a2+a1=2n，则有a2-a0=1.另一方面，对于i∈F，如果li=2，那么li-1=li+1=0（若i-1或i+1存在）.所以a2-a0≤1，且等号成立当且仅当l0=l2=l4=…=lp=

2且l1=l3=l5=…=lp-1=0.故[y，z]中至多有「（z-y）/2=「（n-1）/2＜n-2个整数在f下出现，不足以两两不同地标B{u′，v′}中的n-2个顶点，矛盾.

情形2.2 z-y=n-2.

另一方面，由z-y=n-2可得[y，z]中恰有1个整数不在f（B{u′，v′}）中出现.又当li=2时，有li-1=li+1=0.因而，在f（V（G）{u，v，u′，v′}）中，除y和z以外的整数都不会出现2次，并且y和z最多有一个出现2次.另外，注意到{u，v}∪B中的顶点标号都是两两不同的，{u′，v′}∪A中的顶点标号也是两两不同的.所以，如果y和z的其中一个在f下出现2次（不妨设其为y），则恰有2n-1个顶点的标号两两不同，并且标[0，p]{y-1，y+1}中的整数.此时可得p≥2n，矛盾.故所有标号最多只能出现1次，即p≥2n-1.因此p=2n-1，即[0，2n-1]中的每个标号恰好出现一次.

如果y-1被标在u′（v′）上，则y-2只能标在v′（u′）上.但此时没有顶点可以标y-3（其中y-3≥2），所以y-1只能标在A中的顶点上.进而可得[1，y-1]中的所有标号都只能标在A中的顶点上.类似以上讨论，可得[z+1，2n-2]中的所有标号只能标在A中的顶点上.那么只有[y，z]f（B{u′，v′}），这个唯一的整数可以用来标u′和v′，这与它们的标号不同矛盾.

情形2.3 z-y=n-3.

此时，f（B{u′，v′}）是[y，z]中n-2个连续整数.所以B{u′，v′}中顶点的标号两两不同，从而V（G）中顶点的标号两两不同.故p≥2n-1.

如果p=2n-1，则[0，2n-1]中的整数恰好各出现1次.此时有[0，y-1]∪[z+1，2n-1]⊆f（A），则没有整数可以用来标u′和v′，矛盾.

如果p=2n，则[0，2n]中恰有1个整数在f下不出现.另一方面，由于2n-「3n/2+2≤f（u′）≤2n-2且2≤f（v′）≤「3n/2-2，则f（u′）-1、f（u′）+1、f（v′）-1、f（v′）+1∈[0，2n]都存在且都不等于0或p.此外，由于f（B{u′，v′}）为连续整数，故f（u′）-1、f（u′）+1不能同时出现在[y，z]中，f（v′）-1、f（v′）+1也不能同时出现在[y，z]中.因此f（u′）-1、f（u′）+1、f（v′）-1、f（v′）+1中至少有1个出现在A{u，v}的顶点上.这会产生矛盾，因为u′、v′与A{u，v}中的顶点都是相邻的.综上，β（G，f）≥「3n/2-1.由f的任意性知结论成立.证毕.

[1]GRIGGS J R，YEH R K.Labeling graph with a condition at distance two[J].SIAM J Discrete Math，1992，5：586-595.

[2]BODLAENDER H L，KLOKS T，TAN R B，et al.λ-coloring of graphs [C]//STACS’00:Proceedings of the 17th Annual Symposium on TheoreticalAspectsofComputerScience，London：Springer-Verlag，2000：395-406.

[3]WANG W F.The L（2，1）-labeling of trees[J].Discrete Appl Math，2007，154：598-603.

[4]ZHANG X L.Distance two labeling on the square of a cycle[J].Korean J Math，2015，23（4）：607-618.

[5]HAQUEE，JHAPK.L（j，k）-labelings of Kroneckerproductsof complete graphs[J].IEEE Trans Circuits Syst II，2008，55：70-73.

[6]ZHU H Y，HOU L F，CHEN W，et al.The L（p，q）-labeling of planar graphs without 4-cycles[J].Discrete Appl Math，2014，162：355-363.

[7]YEH R K.A survey on labeling graphs with a condition at distance two [J].Discrete Math，2006，306（12）：1217-1231.

[8]CALAMONERI T.The L（h，k）-labeling problem：An updated survey and annotated bibliography[J].Comput J，2011，54：1344-1371.

[9]LIU D D F，ZHU X D.Circulant distant two labeling and circular chromatic number[J].Ars Combin，2003，69：73-84.

[10]GRIGGS J R.Real number channel assignments with distance conditions[J].SIAM J Discrete Math，2006，20：302-327.

[11]LIH K W.The Equitable Coloring of Graphs[M]//Du D Z，PARDALOS P M.Handbook of Combinatorial Optimization，Boston：Kluwer，1999：543-566.

[12]YEH R K.The edge span of distance two labelings of graphs[J]. Taiwanese J Math，2000，4：675-683.

[13]FENG G Z，SONG Z M.Edge span of L（d，1）-labeling on some graphs [J].J Southeast Univ：Eng Ed，2005，21（1）：111-114.

[14]NIU Q J，LIN W S，SONG Z M.L（s，t）edge spans of trees and product of two paths[J].J Southeast Univ:Eng Ed，2007，23（4）：639-642.

[15]DAI B Q，LIN W S.Real edge spans of distance two labelings of graphs [J].J Southeast Univ：Eng Ed，2009，25（4）：557-562.

[16]ZHANG X L，QIAN J G.L（p，q）-labeling and integer flow on planar graphs[J].Comput J，2013，56：785-792.

[17]ZHANG X L，QIAN J G.L（p，q）-labeling and integer tension of a graph embedded on torus[J].J Comb Optim，2016，31（1）：67-77.

[18]ZHANG X L.Edge span of distance two labeling of digraphs[J].Journal of Mathematical Study，2013，46（4）：418-423.

[19]LIU D D F，YEH R K.On distance two labelings of graphs[J].Ars Combin，1997，47：13-22.

（责任编校 马新光）

Edge spans of distance labelings for almost complete bipartite graphs

ZHANG Xiaoling
（College of Mathematical and Computer Science，Quanzhou Normal University，Quanzhou 362000，Fujian Province，China）

L（1，1）and L（2，1）edge spans for almost complete bipartite graphs（Kn，nwith a 1-factor removed）are studied. L（1，1）edge span is determined based on L（1，1）span of the graphs.The upper bound of L（2，1）edge span is given by properly labeling the graphs,and then the exact value of L（2，1）edge span is determined by using reduction to absurd it.

almost complete bipartite graphs；1-factor；distance labeling；edge span

O157.5

A

1671-1114（2016）04-0010-03

2015-10-30

福建省自然科学基金青年创新资助项目（2015J05013）.

张小玲（1986—），女，讲师，主要从事应用图论方面的研究.