幾乎完全二部圖的距離標號邊跨度

張小玲

（泉州師范學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院，福建泉州362000）

幾乎完全二部圖的距離標號邊跨度

張小玲

（泉州師范學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院，福建泉州362000）

研究幾乎完全二部圖（即完全二部圖Kn，n去掉一個1-因子）的L（1，1）和L（2，1）邊跨度.基于圖的L（1，1）跨度確定了L（1，1）邊跨度.通過給出具體標號得到圖的L（2，1）邊跨度的上界，進而利用反證法確定了L（2，1）邊跨度的確切值.

幾乎完全二部圖；1-因子；距離標號；邊跨度

1 引言及主要結(jié)果

圖的距離標號問題源于無線電網(wǎng)絡(luò)中的頻率分配問題，1992年，Griggs等[1]將其抽象為圖的距離標號問題，并考慮了更一般的L（j，k）-標號.給定正整數(shù)j和k（j≥k），圖G的L（j，k）-標號為定義在V（G）上值域為非負整數(shù)的函數(shù)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）-標號問題最初的優(yōu)化目標是確定圖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].在一些特殊需要的驅(qū)動下，除了圖的跨度之外，還有許多關(guān)于L（j，k）-標號的指標被提出來.如，圓距離標號下的跨度[9]、實數(shù)意義下的距離標號跨度[10]、平衡距離標號下的跨度[11]、圖的距離標號邊跨度[12]等.

本研究考慮圖的距離標號邊跨度.假設(shè)圖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）.與圖的跨度相比，圖的邊跨度是一個局部優(yōu)化的目標函數(shù)，因此不會超過圖的跨度，即βj，k（G）≤λj，k（G）.圖的邊跨度概念最早由Yeh[12]提出，同時確定了圈、樹、完全多部圖、三角格圖和四角格圖的L（2，1）邊跨度.文獻[13]研究了一些特殊圖類的L（d，1）邊跨度.此后，樹及2條路的乘積圖的L（j，k）邊跨度[14]、圈及完全多部圖的實數(shù) L（j，k）邊跨度[15]也被確定.區(qū)別于以往求邊跨度的方法，文獻[16-18]借助整數(shù)流和Tension理論研究了平面圖[16]、非平面圖[17]和有向圖[18]的邊跨度.

圖G的1-因子是指每個點僅關(guān)聯(lián)1條邊的G的生成子圖.本研究記M為完全二部圖Kn，n的一個1-因子.設(shè)V′和E′分別為V（G）和E（G）的非空子集，定義G-V′為G去掉V′以及V′中的頂點所關(guān)聯(lián)的邊之后的

子圖，G-E′為G去掉E′之后的子圖.完全二部圖Kn，n去掉一個1-因子M之后得到的圖，即Kn，n-M，稱為幾乎完全二部圖.本研究考慮Kn，n-M的L（1，1）及L（2，1）邊跨度，得到如下結(jié)果：

定理1 設(shè)n≥5，則β1，1（Kn，n-M）=n-1.

定理2 設(shè)n≥8，則β（Kn，n-M）=「3n/2-1.

2 主要結(jié)果的證明

引理[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.

另一方面，假設(shè)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.證畢.

對于整數(shù)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所示.現(xiàn)給出G的標號：

圖1 幾乎完全二部圖GFig.1 Almost complete bipartite graph G

下面考慮β（G）的下界.設(shè)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在不同部.不失一般性，設(shè)u∈A且v∈B.

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

如果u1∈A或v1∈B，則G1同構(gòu)于完全二部圖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同構(gòu)于Kn-2，n-2去掉一個1-因子）.令如果u2∈A，則

如果u2∈B，則

情形2 u和v在同一部.不失一般性，設(shè)u、v∈A，則B中頂點的標號都不同于u和v的標號，否則

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

設(shè)uu′、vv′∈M，其中u′、v′∈B.令z和y分別為f在B{u′，v′}中的最大標號和最小標號.使用反證法.假設(shè)β（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.

設(shè)ai為L中的標號在f下出現(xiàn)i的個數(shù)，即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，且等號成立當(dāng)且僅當(dāng)l0=l2=l4=…=lp=

2且l1=l3=l5=…=lp-1=0.故[y，z]中至多有「（z-y）/2=「（n-1）/2＜n-2個整數(shù)在f下出現(xiàn)，不足以兩兩不同地標B{u′，v′}中的n-2個頂點，矛盾.

情形2.2 z-y=n-2.

另一方面，由z-y=n-2可得[y，z]中恰有1個整數(shù)不在f（B{u′，v′}）中出現(xiàn).又當(dāng)li=2時，有l(wèi)i-1=li+1=0.因而，在f（V（G）{u，v，u′，v′}）中，除y和z以外的整數(shù)都不會出現(xiàn)2次，并且y和z最多有一個出現(xiàn)2次.另外，注意到{u，v}∪B中的頂點標號都是兩兩不同的，{u′，v′}∪A中的頂點標號也是兩兩不同的.所以，如果y和z的其中一個在f下出現(xiàn)2次（不妨設(shè)其為y），則恰有2n-1個頂點的標號兩兩不同，并且標[0，p]{y-1，y+1}中的整數(shù).此時可得p≥2n，矛盾.故所有標號最多只能出現(xiàn)1次，即p≥2n-1.因此p=2n-1，即[0，2n-1]中的每個標號恰好出現(xiàn)一次.

如果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′}），這個唯一的整數(shù)可以用來標u′和v′，這與它們的標號不同矛盾.

情形2.3 z-y=n-3.

此時，f（B{u′，v′}）是[y，z]中n-2個連續(xù)整數(shù).所以B{u′，v′}中頂點的標號兩兩不同，從而V（G）中頂點的標號兩兩不同.故p≥2n-1.

如果p=2n-1，則[0，2n-1]中的整數(shù)恰好各出現(xiàn)1次.此時有[0，y-1]∪[z+1，2n-1]?f（A），則沒有整數(shù)可以用來標u′和v′，矛盾.

如果p=2n，則[0，2n]中恰有1個整數(shù)在f下不出現(xiàn).另一方面，由于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′}）為連續(xù)整數(shù)，故f（u′）-1、f（u′）+1不能同時出現(xiàn)在[y，z]中，f（v′）-1、f（v′）+1也不能同時出現(xiàn)在[y，z]中.因此f（u′）-1、f（u′）+1、f（v′）-1、f（v′）+1中至少有1個出現(xiàn)在A{u，v}的頂點上.這會產(chǎn)生矛盾，因為u′、v′與A{u，v}中的頂點都是相鄰的.綜上，β（G，f）≥「3n/2-1.由f的任意性知結(jié)論成立.證畢.

[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.

（責(zé)任編校 馬新光）

Edge spans of distance labelings for almost complete bipartite graphs

ZHANG Xiaoling
（College of Mathematical and Computer Science，Quanzhou Normal University，Quanzhou 362000，F(xiàn)ujian 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

福建省自然科學(xué)基金青年創(chuàng)新資助項目（2015J05013）.

張小玲（1986—），女，講師，主要從事應(yīng)用圖論方面的研究.