童细心

(汕头职业技术学院 自然科学系,广东 汕头　515041)



棒棒糖图的优美性和平衡性

童细心

(汕头职业技术学院 自然科学系,广东 汕头515041)

摘要：给出了棒棒糖图Cn+Pl在n=4k时的优美标号，得到了棒棒糖图Cn+Pl在n=4k时是优美图等结论。

关键词：棒棒糖图；优美图；交错图；平衡图

1引言与预备知识

优美图是图论中一个十分有趣且重要的内容,它的提出始于1963年G.Ringel[1]的一个猜想,目前其研究成果已经被广泛应用于射电天文学、X-射线衍射晶体学、密码设计、通信网络编址、导弹控制码设计、同步机码设计、交通物流控制等领域,至今关于优美图的研究已得到了很多结果[1-10]。

定义1[11]对于简单图G=(V,E),若∀v∈V,存在单射f(v)∈{0,1,2,…,|E|}(f(v)称为顶点v的标号),且导出的边标号f′(e)=f′(uv)=|f(u)-f(v)|是E到{1,2,3,…,|E|}的双射,则称图G是优美图,称f为图G的优美标号。

定义2[11]对于简单图G=(V,E),若顶点集V(G)能分成2个非空子集X和Y，使得X∪Y=V(G)，X∩Y=φ，且G的每条边的端点分别在X和Y中，则称G为二分图，记作G=(X,Y;E)，二分划记为(X,Y)；如果G还是优美图，则称G为优美二分图。

定义4[11]设f为G的一个优美标号，若存在正整数λ，使得对任意uv∈E(G)，都有f(u)≤λ

定义5[12]从圈Cn上的一个顶点vn悬挂一条长为l的路Pl所得到的图类,称为棒棒糖图,记为Cn+Pl。如图1所示,我们记圈Cn的顶点为vi,i=1,2,…,n。路Pl的顶点为vn+i,i=1,2,…,l。

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

本文研究了棒棒糖图的优美性,平衡性。文中所讨论的图均为无向简单图,点v2p称为偶点,v2p-1称为奇点。其他未加说明的定义和符号均来自文[13]。

2主要结果

2.1情形1当n=4k,l=2t时,棒棒糖图Cn+Pl的顶点数和边数均为n+l=4k+2t。给出棒棒糖图Cn+Pl的各顶点的标号递推算法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可得以下结果:

引理1当n=4k,l=2t时,棒棒糖图Cn+Pl的顶点集与集合{0,1,2,…,4k+2t}构成单射。

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

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

又f(v4k+2t-1)=2k+t<2k+t+1=f(v4k+2t)，奇点中最大标号都小于偶点中的最小标号，故奇点与偶点标号也互不相同。

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

综上，当n=4k,l=2t时, 棒棒糖图Cn+Pl的顶点集与集合{0,1,2,…,4k+2t}构成单射。

引理2当n=4k,l=2t时,棒棒糖图Cn+Pl的边集与集合{1,2,3,…,4k+2t}构成双射。

证明由引理1知,minf(vi)=f(v1)=0,maxf(vi)=f(v2)=4k+2t,故边的标号均不超过4k+2t。依照算法A把边的标号分为以下几种情况来考虑：

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。

根据以上5种情况，易得边的标号对应的集合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。

综上所述,当n=4k,l=2t时, 棒棒糖图Cn+Pl的边集与集合{1,2,3,…,4k+2t}构成双射。

定理1当n=4k,l=2t时, 棒棒糖图Cn+Pl是优美图。

证明由引理1、引理2及定义1知,定理1成立。

定理2当n=4k,l=2t时, 棒棒糖图Cn+Pl是交错图和平衡图，且平衡特征为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当n=4k,l=2t+1时,棒棒糖图Cn+Pl的顶点数与边数均为n+l=4k+2t+1。给出棒棒糖图Cn+Pl的各顶点的标号递推算法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可得以下结果:

引理3当n=4k,l=2t+1时,棒棒糖图Cn+Pl的顶点集与集合{0,1,2,…,4k+2t+1}构成单射。

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

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

又f(v4k+2t+1)=2k+t+1<2k+t+2=f(v4k+2t)，奇点中最大标号都小于偶点中的最小标号，故奇点与偶点标号也互不相同。

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

综上，当n=4k,l=2t+1时, 棒棒糖图Cn+Pl的顶点集与集合{0,1,2,…,4k+2t+1}构成单射。

引理4当n=4k,l=2t+1时,棒棒糖图Cn+Pl的边集与集合{1,2,3,…,4k+2t+1}构成双射。

证明由引理3知,minf(vi)=f(v1)=0,maxf(vi)=f(v2)=4k+2t+1,故边的标号均不超过4k+2t+1。依照算法B把边的标号分为以下几种情况来考虑：

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。

依照以上五种情况，易得边的标号对应的集合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。

综上所述,当n=4k,l=2t+1时, 棒棒糖图Cn+Pl的边集与集合{1,2,3,…,4k+2t+1}构成双射。

定理3当n=4k,l=2t+1时, 棒棒糖图Cn+Pl是优美图。

证明由引理3、引理4及定义1知,定理3成立。

定理4当n=4k,l=2t+1时, 棒棒糖图Cn+Pl是交错图和平衡图，且平衡特征为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结束语

研究证明了棒棒糖图Cn+Pl在n=4k时是优美图、交错图及平衡图的结论。对于n=4k-1,4k+1,4k+2时，有如下猜想：

猜想1：当n=4k-1,4k+1时,棒棒糖图Cn+Pl是优美图。

猜想2：当n=4k+2,l>1时,棒棒糖图Cn+Pl不是优美图。

最后按照算法A、B，分别得到棒棒糖图C12+P10，C16+P9的优美标号如下图示：

图2　棒棒糖图C12+P10的优美标号Fig.2　Graceful labeling of Lollipop graph C12+P10

图3　棒棒糖图C16+P9的优美标号Fig.3　Graceful labeling of Lollipop graph C16+P9

参考文献：

[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] 林育青.一类图的优美性[J].云南师范大学学报(自然科学版),2004,24(4):15-19.

[6] 林育青.Cn与1Cn的优美标号[J].安徽大学学报(自然科学版),2007,32(2):13-16.

[7] 林育青.毛毛虫树T(k1,k2,…,kn)的优美标号[J].山西师范大学学报(自然科学版),2007,21(2):34-38.

[8] 张玲瑛,林育青,钟发胜,童细心.关于图2×Cn的标号[J].北华大学学报(自然科学版), 2014,15(2):174-178.

[10]童细心.一类哑铃图的优美性和奇强协调性[J].汕头大学学报(自然科学版), 2015,30(2):38-43.

[11]马克杰.优美图[M].北京:北京大学出版社,1991.

[12]陈暑波,夏方礼,龙韬,等.棒棒糖图的Merrifield-Simmons和Hosoya指数[J]. 湖南城市学院学报(自然科学版),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

基金项目：汕头职业技术学院2015年院级科研课题(SZK2015Y23)

作者简介：童细心(1979-),男，讲师,硕士,研究方向:图论,E-mail：txx2486@126.com.

中图分类号：O157.5

文献标识码：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