一類具有不同島序列的連通圖

趙小玲

(上海電機學院 數理教學部，上海 201306)

一類具有不同島序列的連通圖

趙小玲

(上海電機學院 數理教學部，上海 201306)

令G=(V，E)是一個簡單圖，圖G的L(2,1)標號是一個映射f:V(G)→{0,1,…}，使得對任意的u,v∈V(G)，若dG(u,v)=1,則|f(u)-f(v)|≥2;若dG(u,v)=2,則|f(u)-f(v)|≥1。基于圖G的L(2,1)標號與其補圖GC的路覆蓋之間存在著對應的關系，通過對補圖的不同路覆蓋的研究，得到了一類具有至少兩個不同島序列的特殊的連通圖——M-圈串圖的補圖。

L(2,1)標號; 洞指數; 島序列; 連通圖

頂點的距離-2標號問題來源于Hale所介紹的頻道分配問題，最早在文獻[1]中進行了研究。假設給定一些無線電發射臺，必須給每個電臺分配一個頻道且要避免頻道之間相互干擾。用非負整數代表不同的頻道，為減少干擾，任何兩個“接近”的電臺必須分配到不同的頻道，任何兩個“非常接近”的電臺必須分配到距離至少為2的頻道。為了解決該問題，可以構作這樣的一個簡單無向圖G=(V，E)：頂點u和v之間的距離是u和v之間的最短路的長度，記作dG(u,v)。若兩個頂點是“非常接近”的，則在圖中它們是相鄰的；若兩個頂點是“接近”的，則它們在圖中的距離為2。

圖G的L(2,1)標號是映射f:V(G)→{0,1,…}，使得對任意的u,v∈V(G)，若dG(u,v)=1,則|f(u)-f(v)|≥2;若dG(u,v)=2,則|f(u)-f(v)|≥1。圖G的k-L(2,1)標號是圖G的一個L(2,1)標號，使得所用到的標號最大為k；圖G的L(2,1)標號數記作λ(G)，定義為[2]λ(G)=min{k|G有一個k-L(2,1)標號}。若圖G的k-L(2,1)標號中標號h(0

由于在交叉學科和應用領域中的重要性，圖G的L(2,1)標號問題得到了廣泛研究。作為L(2,1)標號的一個重要特征，圖G的島序列也成為了一個主要的研究方向。文獻[3-4]中對此作了很多研究。一些不連通圖，由于它們的結構比較疏松，較容易得到它們的一些具有不同島序列的λ(G)-L(2,1)標號。那么，對于結構比較緊密的連通圖是否也有此結論？文獻[3]中提出了一個公開問題：是否存在一些連通圖至少具有2個λ標號的不同島序列？

基于圖G的L(2,1)標號與其補圖GC的路覆蓋之間存在著的對應關系，本文主要通過探討其補圖的不同的路覆蓋，得到了一類至少有兩個λ標號的不同島序列的連通圖：M-圈串圖的補圖。本文中未詳細描述的術語和符號參見文獻[5-6]，文中涉及的一些其他線索可參考文獻[7-13]。

1 理論基礎

有些圖，它們不同的λ(G)標號有相同的島序列，如圖1中的完全二分圖K2,3的兩個不同的λ=5,ρ=1的標號，有相同的島序列(2,3)；而有些圖，它們不同的λ(G)標號對應有不同的島序列，如圖

2中的不連通圖K4∪P2的2個不同的λ=6,ρ=1的標號，有不同的島序列(5,1)和(3,3)。

圖1 K2,3的2個λ-L(2,1)標號Fig.1 Two λ-L(2,1) labelings of K2,3

圖2 K4∪P2的2個λ-L(2,1)標號Fig.2 Two λ-L(2,1) labelings of K4∪P2

那么，對于連通圖，是否可能至少具有2個不同的λ標號的島序列？本文考察M-圈串圖G的路覆蓋和它的補圖GC的島序列。

定義1G=(V,E)是一個簡單圖，圖G的一個路覆蓋是指G中包含了所有頂點的點不交路的集合。圖G的具有最少路數的一個路覆蓋中路的數目稱為圖G的路覆蓋數，用P(G)表示。恰有P(G)條路的一個路覆蓋稱為圖G的最小路覆蓋。

定義2不包含相鄰的且度數大于2的頂點對的圖稱為2-稀疏圖。

定義3由M+1條長度大于1的路連接M個點不交的圈形成的圖稱為M-圈串圖，如圖3所示。顯然M圈串圖是一個有2個葉子的2-稀疏圖。

圖3 M-圈串圖Fig.3 M-circles string

引理1[14]令G是一個有m≥1條邊、n個頂點、l個葉子的2-稀疏圖。若G不是圈圖，則P(G)=l+m-n。

引理2[15]令G是一個有n個頂點的圖，則λ(G)=n+P(GC)-2，當且僅當P(G)≥2。

引理3[3]令G是一個有n個頂點的圖，若λ(G)≥n-1，則ρ(G)=P(GC)-1。

2 主要結論

定理1令G是一個M-圈串圖，則GC是連通圖。

證明設w1、w2是M-圈串圖G的兩個葉子，u和v是G中任意兩個不同的頂點。

若u和v恰好是w1和w2，則由于w1、w2是M-圈串圖的兩個葉子，它們在G中不相鄰，故w1、w2在GC相鄰。此時w1w2(即uv)是GC中連通u和v的一條路。以下假設u和v均不是w1或w2。

情況1u和v在GC中相鄰，則uv為GC中連通u和v的一條路。

情況2u和v在GC中不相鄰。

(1)u和v在G中均不與wi(i=1,2)相鄰，則u和v在GC中均與wi(i=1,2)相鄰，此時，uw1v或uw2v都是GC中連通u和v的一條路。

(2)u和v中的一個在G中與wi(i=1,2)中的一個相鄰，另一個在G中與wi(i=1,2)均不相鄰。不失一般性，設u在G中與w1相鄰，v在G中與wi(i=1,2)均不相鄰。此時，u在GC中與

w2相鄰，v在GC中也與w2相鄰，因此，uw2v是GC中連通u和v的一條路。

(3)u和v中的一個在G中分別與wi(i=1,2)中的一個相鄰。不失一般性，設u在G中與w1相鄰，v在G中與w2相鄰，則在GC中，u與w2相鄰，v與w1相鄰。又因為w1、w2是M-圈串圖的兩個葉子，它們在G中不相鄰，故w1、w2在GC中相鄰。此時，uw2w1v是GC中連通u和v的一條路。

綜上所述，G中的任意兩個不同的頂點u和v在GC中都是連通的，故GC是連通圖。 證畢

定理2令G是一個M-圈串圖，則GC至少有2個不同的λ標號的島序列。

證明由定義3可知，若G是一個有n個頂點、m條邊的M-圈串圖，則m=n+M-1。由引理1，

P(G)=l+m-n=2+(n+M-1)-n=M+1

本文給出G的2個最小路覆蓋以及對應的GC的島序列。

(1) 如圖4所示，令P1=u11u12…u1n1；P2=u21u22…u2n2；…；PM=uM1uM2…uMnM；PM+1=u(M+1)1u(M+1)2…u(M+1)nM+1。

圖4 M-圈串圖的一個路覆蓋Fig.4 A path covering of M-circles string

對應此最小路覆蓋，得到如下GC的L(2,1)標號：

f(u1i)=i-1, i=1,2,…,n1

f(u2i)=n1+i, i=1,2,…,n2

?

f(uMi) =n1+n2+…+nM-1+ i+M-2, i=1,2,…,nM

f(u(M+1)i)=n1+n2+…+nM+i+ M-1, i=1,2,…,nM+1

此時，標號f的標號數為

n1+n2+…+nM+nM+1+M-1=

n+M-1=n+(M+1)-2= n+P(G)-2

由引理2，有

n+P(G)-2=λ(GC)

故標號f為GC的一個λ-L(2,1)標號。

又由引理3，有

ρ(GC)=P(G)-1=M+1-1=M

可得到GC的一個有M個洞的λ標號的島序列(n1,n2,…,nM,nM+1)。

對應此最小路覆蓋，得到GC的L(2,1)標號：

圖5 M-圈串圖的另一個路覆蓋Fig.5 Another path covering of M-circles string

此時標號f′的標號數為

l1+l2+…+lM+lM+1+M-1=n+M-1=n+(M+1)-2=n+P(G)-2

由引理2，有

n+P(G)-2=λ(GC)

故標號f′也是GC的一個λ-L(2,1)標號。

又由引理3，有

ρ(GC)=P(G)-1=M+1-1=M

可得到GC的一個有M個洞的λ標號的島序列(l1,l2,…,lM,lM+1)。

因此，M-圈串圖的補圖是一類具有不同島序列的連通圖。

證畢

[1] GRIGGS J R，YEH R K.Labelling graphs with a condition at distance 2[J].SIAM Journal on Discrete Mathematics,1992,5(4):586-595.

[2] CHANG G J,KUO D.TheL(2,1)-Labeling problem on graphs[J].SIAM Journal on Discrete Mathematics,1996,9(2):309-316.

[3] GEORGES J P,MAURO D W. On the structure of graphs with non-surjectiveL(2,1)-labelings[J].SIAM Journal on Discrete Mathematics,2005,19(1):208-223.

[4] GEORGES J P,MAURO D W.A note on collections of graphs with non-surjectiveL(2,1)-labelings[J].Discrete Applied Mathematics,2005,146(1):92-98.

[5] WEST D B.Introduction to Graph Theory[M].2nd ed.Upper Saddle River,NJ.Prentice Hall,Inc,2001.

[6] BONDY J A，MURTY U S R.Graph theory with applications[M].London:The Macmillan Press,Ltd,1976.

[7] FISHBURN P C,ROBERTS F S.No-holeL(2,1)-coloring[J].Discrete Applied Mathematics,2003,130(3):513-519.

[8] CHANG G J,LU Changhong.Distance-two labelings of graphs[J].European Journal of Combinatorics, 2003,24 (1):53-58.

[9] SHAO Zhendong, LIU Jiazhuang.TheL(2,1)-labeling problem on several classes of graphs[J].Mathematica Applicata,2004,17(1)：31-36.

[10] GEORGES J P,MAURO D W.On the structure of graphs with non-surjectiveL(2,1)-labelings[J].SIAM Journal on Discrete Mathematics,2005,19(1):208-223.

[11] YEH R K.A survey on labeling graphs with a condition at distance two[J].Discrete Mathematics,2006,306(12):1217-1231.

[12] LU Changhong,CHEN Lei, ZHAI Mingqing.Extremal problems on consecutiveL(2,1)-labellings[J].Discrete Applied Mathematics,2007,155(10):1302-1313.

[13] LU Changhong,ZHAI Mingqing.An extremal problem on non-full colorable graphs[J].Discrele Applied Mathematics,2007,155(16):2165-2173.

[14] ADAMS S S,TRAZKOVICH A,TROXELL D S,et al.On island sequences of labelings with a condition at distance two[J].Discrete Applied Mathematics,2010,158(1):1-7.

[15] GEORGES J P,MAURO D W,WHITTLESEY M A.Relating path covering to vertex labelings with a condition at distance two[J].SIAM Journal on Discrete Mathematics,1994,135(1/3):103-111.

A Class of Connected Graphs with Multiple Island Sequence

ZHAO Xiaoling

(Department of Mathematics and Physics, Shanghai Dianji University, Shanghai 201306, China)

LetG=(V，E) be a simple graph. TheL(2,1)-labeling ofGis a functionf:V(G)→{0,1,…} such that anyu,v∈V(G),|f(u)-f(v)|≥2 ifdG(u,v)=1, and |f(u)-f(v)|≥1 if,dG(u,v)=2.Based on the relation between theL(2,1)-labeling ofGand the path covering ofGC, we observe different path covering of the complement ofGand reach a class of connected graphs with multiple island sequence —the complement ofM-circles string.

L(2,1)-labeling; hole index; island sequence; connected graph

2016-05-16

趙小玲(1970-)，女，副教授，主要研究方向為圖論及其應用，E-mail:zhaoxl@sdju.edu.cn

2095-0020(2016)06-0369-04

O 157.5

A