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

趙小玲

(上海電機(jī)學(xué)院 數(shù)理教學(xué)部，上海 201306)

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

趙小玲

(上海電機(jī)學(xué)院 數(shù)理教學(xué)部，上海 201306)

令G=(V，E)是一個(gè)簡單圖，圖G的L(2,1)標(biāo)號是一個(gè)映射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)標(biāo)號與其補(bǔ)圖GC的路覆蓋之間存在著對應(yīng)的關(guān)系，通過對補(bǔ)圖的不同路覆蓋的研究，得到了一類具有至少兩個(gè)不同島序列的特殊的連通圖——M-圈串圖的補(bǔ)圖。

L(2,1)標(biāo)號; 洞指數(shù); 島序列; 連通圖

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

圖G的L(2,1)標(biāo)號是映射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)標(biāo)號是圖G的一個(gè)L(2,1)標(biāo)號，使得所用到的標(biāo)號最大為k；圖G的L(2,1)標(biāo)號數(shù)記作λ(G)，定義為[2]λ(G)=min{k|G有一個(gè)k-L(2,1)標(biāo)號}。若圖G的k-L(2,1)標(biāo)號中標(biāo)號h(0

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

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

1 理論基礎(chǔ)

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

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

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

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

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

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

定義2不包含相鄰的且度數(shù)大于2的頂點(diǎn)對的圖稱為2-稀疏圖。

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

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

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

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

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

2 主要結(jié)論

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

證明設(shè)w1、w2是M-圈串圖G的兩個(gè)葉子，u和v是G中任意兩個(gè)不同的頂點(diǎn)。

若u和v恰好是w1和w2，則由于w1、w2是M-圈串圖的兩個(gè)葉子，它們在G中不相鄰，故w1、w2在GC相鄰。此時(shí)w1w2(即uv)是GC中連通u和v的一條路。以下假設(shè)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)相鄰，此時(shí)，uw1v或uw2v都是GC中連通u和v的一條路。

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

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

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

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

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

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

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

本文給出G的2個(gè)最小路覆蓋以及對應(yīng)的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-圈串圖的一個(gè)路覆蓋Fig.4 A path covering of M-circles string

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

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

此時(shí)，標(biāo)號f的標(biāo)號數(shù)為

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

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

由引理2，有

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

故標(biāo)號f為GC的一個(gè)λ-L(2,1)標(biāo)號。

又由引理3，有

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

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

對應(yīng)此最小路覆蓋，得到GC的L(2,1)標(biāo)號：

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

此時(shí)標(biāo)號f′的標(biāo)號數(shù)為

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

由引理2，有

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

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

又由引理3，有

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

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

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

證畢

[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-)，女，副教授，主要研究方向?yàn)閳D論及其應(yīng)用，E-mail:zhaoxl@sdju.edu.cn

2095-0020(2016)06-0369-04

O 157.5

A