棒棒糖圖的優(yōu)美性和平衡性

童細(xì)心

(汕頭職業(yè)技術(shù)學(xué)院 自然科學(xué)系,廣東 汕頭　515041)

?

棒棒糖圖的優(yōu)美性和平衡性

童細(xì)心

(汕頭職業(yè)技術(shù)學(xué)院 自然科學(xué)系,廣東 汕頭515041)

摘要：給出了棒棒糖圖Cn+Pl在n=4k時(shí)的優(yōu)美標(biāo)號，得到了棒棒糖圖Cn+Pl在n=4k時(shí)是優(yōu)美圖等結(jié)論。

關(guān)鍵詞：棒棒糖圖；優(yōu)美圖；交錯(cuò)圖；平衡圖

1引言與預(yù)備知識

優(yōu)美圖是圖論中一個(gè)十分有趣且重要的內(nèi)容,它的提出始于1963年G.Ringel[1]的一個(gè)猜想,目前其研究成果已經(jīng)被廣泛應(yīng)用于射電天文學(xué)、X-射線衍射晶體學(xué)、密碼設(shè)計(jì)、通信網(wǎng)絡(luò)編址、導(dǎo)彈控制碼設(shè)計(jì)、同步機(jī)碼設(shè)計(jì)、交通物流控制等領(lǐng)域,至今關(guān)于優(yōu)美圖的研究已得到了很多結(jié)果[1-10]。

定義1[11]對于簡單圖G=(V,E),若?v∈V,存在單射f(v)∈{0,1,2,…,|E|}(f(v)稱為頂點(diǎn)v的標(biāo)號),且導(dǎo)出的邊標(biāo)號f′(e)=f′(uv)=|f(u)-f(v)|是E到{1,2,3,…,|E|}的雙射,則稱圖G是優(yōu)美圖,稱f為圖G的優(yōu)美標(biāo)號。

定義2[11]對于簡單圖G=(V,E),若頂點(diǎn)集V(G)能分成2個(gè)非空子集X和Y，使得X∪Y=V(G)，X∩Y=φ，且G的每條邊的端點(diǎn)分別在X和Y中，則稱G為二分圖，記作G=(X,Y;E)，二分劃記為(X,Y)；如果G還是優(yōu)美圖，則稱G為優(yōu)美二分圖。

定義4[11]設(shè)f為G的一個(gè)優(yōu)美標(biāo)號，若存在正整數(shù)λ，使得對任意uv∈E(G)，都有f(u)≤λ

定義5[12]從圈Cn上的一個(gè)頂點(diǎn)vn懸掛一條長為l的路Pl所得到的圖類,稱為棒棒糖圖,記為Cn+Pl。如圖1所示,我們記圈Cn的頂點(diǎn)為vi,i=1,2,…,n。路Pl的頂點(diǎn)為vn+i,i=1,2,…,l。

圖1　棒棒糖圖Cn+PlFig.1　Lollipop graphs Cn+Pl

本文研究了棒棒糖圖的優(yōu)美性,平衡性。文中所討論的圖均為無向簡單圖,點(diǎn)v2p稱為偶點(diǎn),v2p-1稱為奇點(diǎn)。其他未加說明的定義和符號均來自文[13]。

2主要結(jié)果

2.1情形1當(dāng)n=4k,l=2t時(shí),棒棒糖圖Cn+Pl的頂點(diǎn)數(shù)和邊數(shù)均為n+l=4k+2t。給出棒棒糖圖Cn+Pl的各頂點(diǎn)的標(biāo)號遞推算法A如下:

1)f(v2i-1)=i-1,i=1,2,…,k;f(v2i-1)=i,i=k+1,k+2,…,2k+t;

2)f(v2i)=4k+2t-i+1,i=1,2,…,2k+t。

按照算法A可得以下結(jié)果:

引理1當(dāng)n=4k,l=2t時(shí),棒棒糖圖Cn+Pl的頂點(diǎn)集與集合{0,1,2,…,4k+2t}構(gòu)成單射。

證明由算法A(1)知:f(v1)

由算法A(2)知:f(v4k+2t)

又f(v4k+2t-1)=2k+t<2k+t+1=f(v4k+2t)，奇點(diǎn)中最大標(biāo)號都小于偶點(diǎn)中的最小標(biāo)號，故奇點(diǎn)與偶點(diǎn)標(biāo)號也互不相同。

最后minf(vi)=f(v1)=0,maxf(vi)=f(v2)=4k+2t。

綜上，當(dāng)n=4k,l=2t時(shí), 棒棒糖圖Cn+Pl的頂點(diǎn)集與集合{0,1,2,…,4k+2t}構(gòu)成單射。

引理2當(dāng)n=4k,l=2t時(shí),棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t}構(gòu)成雙射。

證明由引理1知,minf(vi)=f(v1)=0,maxf(vi)=f(v2)=4k+2t,故邊的標(biāo)號均不超過4k+2t。依照算法A把邊的標(biāo)號分為以下幾種情況來考慮：

1)f′(v2i-1v2i)=|f(v2i-1)-f(v2i)|=|(i-1)-(4k+2t-i+1)|=4k+2t-2i+2,其中i=1,2,…,k;

2)f′(v2i-1v2i)=|f(v2i-1)-f(v2i)=|i-(4k+2t-i+1)|=4k+2t-2i+1,其中i=k+1,k+2,…,2k+t;

3)f′(v2iv2i+1)=|f(v2i)-f(v2i+1)|=|(4k+2t-i+1)-[(i+1)-1]|=4k+2t-2i+1,其中i=1,2,…,k-1;

4) f′(v2iv2i+1)=|f(v2i)-f(v2i+1)|=|(4k+2t-i+1)-(i+1)|=4k+2t-2i,其中i=k,k+1,…,2k+t-1;

5)f′(v4kv1)=|f(v4k)-f(v1)|=|(4k+2t-2k+1)-(1-1)|=2k+2t+1。

根據(jù)以上5種情況，易得邊的標(biāo)號對應(yīng)的集合Mi(i=1,2,3,4,5)為:

M1={f′(v2i-1v2i)|i=1,2,…,k}={4k+2t-2i+2|i=1,2,…,k}

={2k+2t+2,2k+2t+4,…,4k+2t};

M2={f′(v2i-1v2i)|i=k+1,k+2,…,2k+t}

={4k+2t-2i+1|i=k+1,k+2,…,2k+t}

={1,3,5,…,2k+2t-1};

M3={f′(v2iv2i+1)|i=1,2,…,k-1}={4k+2t-2i+1|i=1,2,…,k-1}

={2k+2t+3,2k+2t+5,…,4k+2t-1};

M4={f′(v2iv2i+1)|i=k,k+1,…,2k+t-1}

={4k+2t-2i|i=k,k+1,…,2k+t-1}

={2,4,…,2k+2t};

M5={f′(v4kv1)}=2k+2t+1。

綜上所述,當(dāng)n=4k,l=2t時(shí), 棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t}構(gòu)成雙射。

定理1當(dāng)n=4k,l=2t時(shí), 棒棒糖圖Cn+Pl是優(yōu)美圖。

證明由引理1、引理2及定義1知,定理1成立。

定理2當(dāng)n=4k,l=2t時(shí), 棒棒糖圖Cn+Pl是交錯(cuò)圖和平衡圖，且平衡特征為2k+t。

證明記V(G)=X∪Y，其中X={v2i-1},Y={v2i}，顯然X∩Y=?。

由算法A得：

f(X)={f(v2i-1)}={i-1|i=1,2,…,k}∪{i|i=k+1,k+2,…,2k+t}

={0,1,2,…,k-1}∪{k+1,k+2,…,2k+t}；

f(Y)={f(v2i)}={4k+2t-i+1|i=1,2,…,2k+t}

={4k+2t,4k+2t-1,…,2k+t+1}。

2.2情形2當(dāng)n=4k,l=2t+1時(shí),棒棒糖圖Cn+Pl的頂點(diǎn)數(shù)與邊數(shù)均為n+l=4k+2t+1。給出棒棒糖圖Cn+Pl的各頂點(diǎn)的標(biāo)號遞推算法B如下:

1)f(v2i-1)=i-1,i=1,2,…,k;f(v2i-1)=i,i=k+1,k+2,…,2k+t+1;

2)f(v2i)=4k+2t-i+2,i=1,2,…,2k+t。

按照算法B可得以下結(jié)果:

引理3當(dāng)n=4k,l=2t+1時(shí),棒棒糖圖Cn+Pl的頂點(diǎn)集與集合{0,1,2,…,4k+2t+1}構(gòu)成單射。

證明由算法B(1)知:f(v1)

由算法B(2)知:f(v4k+2t)

又f(v4k+2t+1)=2k+t+1<2k+t+2=f(v4k+2t)，奇點(diǎn)中最大標(biāo)號都小于偶點(diǎn)中的最小標(biāo)號，故奇點(diǎn)與偶點(diǎn)標(biāo)號也互不相同。

最后minf(vi)=f(v1)=0,maxf(vi)=f(v2)=4k+2t+1。

綜上，當(dāng)n=4k,l=2t+1時(shí), 棒棒糖圖Cn+Pl的頂點(diǎn)集與集合{0,1,2,…,4k+2t+1}構(gòu)成單射。

引理4當(dāng)n=4k,l=2t+1時(shí),棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t+1}構(gòu)成雙射。

證明由引理3知,minf(vi)=f(v1)=0,maxf(vi)=f(v2)=4k+2t+1,故邊的標(biāo)號均不超過4k+2t+1。依照算法B把邊的標(biāo)號分為以下幾種情況來考慮：

1)f′(v2i-1v2i)=|f(v2i-1)-f(v2i)|=|(i-1)-(4k+2t-i+2)|=4k+2t-2i+3,其中i=1,2,…,k;

2)f′(v2i-1v2i)=|f(v2i-1)-f(v2i)=|i-(4k+2t-i+2)|=4k+2t-2i+2,其中i=k+1,k+2,…,2k+t;

3)f′(v2iv2i+1)=|f(v2i)-f(v2i+1)|=|(4k+2t-i+2)-[(i+1)-1]|=4k+2t-2i+2,其中i=1,2,…,k-1;

4) f′(v2iv2i+1)=|f(v2i)-f(v2i+1)|=|(4k+2t-i+2)-(i+1)|=4k+2t-2i+1,其中i=k,k+1,…,2k+t;

5)f′(v4kv1)=|f(v4k)-f(v1)|=|(4k+2t-2k+2)-(1-1)|=2k+2t+2。

依照以上五種情況，易得邊的標(biāo)號對應(yīng)的集合Ni(i=1,2,3,4,5)分別為:

N1={f′(v2i-1v2i)|i=1,2,…,k}={4k+2t-2i+3|i=1,2,…,k}

={2k+2t+3,2k+2t+5,…,4k+2t+1};

N2={f′(v2i-1v2i)|i=k+1,k+2,…,2k+t}

={4k+2t-2i+2|i=k+1,k+2,…,2k+t}

={2,4,6,…,2k+2t};

N3={f′(v2iv2i+1)|i=1,2,…,k-1}={4k+2t-2i+2|i=1,2,…,k-1}

={2k+2t+4,2k+2t+6,…,4k+2t};

N4={f′(v2iv2i+1)|i=k,k+1,…,2k+t}

={4k+2t-2i+1|i=k,k+1,…,2k+t}

={1,3,…,2k+2t+1};

N5={f′(v4kv1)}=2k+2t+2。

綜上所述,當(dāng)n=4k,l=2t+1時(shí), 棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t+1}構(gòu)成雙射。

定理3當(dāng)n=4k,l=2t+1時(shí), 棒棒糖圖Cn+Pl是優(yōu)美圖。

證明由引理3、引理4及定義1知,定理3成立。

定理4當(dāng)n=4k,l=2t+1時(shí), 棒棒糖圖Cn+Pl是交錯(cuò)圖和平衡圖，且平衡特征為2k+t+1。

證明記V(G)=X∪Y，其中X={v2i-1},Y={v2i}，顯然X∩Y=φ。

由算法B得：

f(X)={f(v2i-1)}={i-1|i=1,2,…,k}∪{i|i=k+1,k+2,…,2k+t+1}

={0,1,2,…,k-1}∪{k+1,k+2,…,2k+t+1}；

f(Y)={f(v2i)}={4k+2t-i+2|i=1,2,…,2k+t}

={4k+2t+1,4k+2t,…,2k+t+2}。

3結(jié)束語

研究證明了棒棒糖圖Cn+Pl在n=4k時(shí)是優(yōu)美圖、交錯(cuò)圖及平衡圖的結(jié)論。對于n=4k-1,4k+1,4k+2時(shí)，有如下猜想：

猜想1：當(dāng)n=4k-1,4k+1時(shí),棒棒糖圖Cn+Pl是優(yōu)美圖。

猜想2：當(dāng)n=4k+2,l>1時(shí),棒棒糖圖Cn+Pl不是優(yōu)美圖。

最后按照算法A、B，分別得到棒棒糖圖C12+P10，C16+P9的優(yōu)美標(biāo)號如下圖示：

圖2　棒棒糖圖C12+P10的優(yōu)美標(biāo)號Fig.2　Graceful labeling of Lollipop graph C12+P10

圖3　棒棒糖圖C16+P9的優(yōu)美標(biāo)號Fig.3　Graceful labeling of Lollipop graph C16+P9

參考文獻(xiàn)：

[1] RINGEL G.Problem 25,in:Theory of Graphs and Its Application [J].Proc Symposium Smolenice,1963,1263:162-167.

[2] GALLIAN J A.A Dynamic Survey of Graph Labeling[J].The Electronic Journal of Combinatorics,2009,16(6):1-219.

[5] 林育青.一類圖的優(yōu)美性[J].云南師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2004,24(4):15-19.

[6] 林育青.Cn與1Cn的優(yōu)美標(biāo)號[J].安徽大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,32(2):13-16.

[7] 林育青.毛毛蟲樹T(k1,k2,…,kn)的優(yōu)美標(biāo)號[J].山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,21(2):34-38.

[8] 張玲瑛,林育青,鐘發(fā)勝,童細(xì)心.關(guān)于圖2×Cn的標(biāo)號[J].北華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014,15(2):174-178.

[10]童細(xì)心.一類啞鈴圖的優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J].汕頭大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,30(2):38-43.

[11]馬克杰.優(yōu)美圖[M].北京:北京大學(xué)出版社,1991.

[12]陳暑波,夏方禮,龍韜,等.棒棒糖圖的Merrifield-Simmons和Hosoya指數(shù)[J]. 湖南城市學(xué)院學(xué)報(bào)(自然科學(xué)版),2008,17(3):39-41.

[13]BANDY J A,MURTY U S R.Graph Theory with Application[M].New York：American Elsevier Publishing Co.,Inc.,1976.

文章編號：1004—5570(2016)03-0056-04

收稿日期：2015-08-07

基金項(xiàng)目：汕頭職業(yè)技術(shù)學(xué)院2015年院級科研課題(SZK2015Y23)

作者簡介：童細(xì)心(1979-),男，講師,碩士,研究方向:圖論,E-mail：txx2486@126.com.

中圖分類號：O157.5

文獻(xiàn)標(biāo)識碼：A

Gracefulness and balance of lollipop graphs

TONG Xixin

(Department of Natural sciences, Shantou Polytechnic, Shantou, Guangdong 515041,China)

Abstract:We show that lollipop graphs Cn+Pl are Graceful when n=4k. Algorithms of graceful labeling for these lollipop graphs are given.

Key words:lollipop graphs; graceful graph ;balanced graph;alternating graph