再探非连通图C4m-1∪C12m-8∪G的优美标号

吴 跃 生

(华东交通大学 理学院, 江西 南昌　330013)



再探非连通图C4m-1∪C12m-8∪G的优美标号

吴 跃 生

(华东交通大学 理学院, 江西 南昌330013)

摘要:讨论了非连通图C4∪C12∪G的优美性,证明了当m为任意正整数,G是特征为k且缺标号值k+6m-4的交错图(6m-4≤k+6m-4≤|E(G)|)时,非连通图C4∪C12∪G存在缺标号值k+16m-9的优美标号,其中,Cspan是具有m个顶点的圈.

关键词:优美图; 平衡二分图; 非连通图; 优美标号

本文所讨论的图均为无向简单图,V(G)和E(G)分别表示图G的顶点集和边集,记号[m,n]表示整数集合{m,m+1,…,n},其中,m和n均为非负整数,且满足0≤m

图的优美标号问题是组合数学中一个热门课题[1-15].文献[12]讨论了非连通图C4m-1∪G的优美性,给出了非连通图C4m-1∪G是优美图的两个充分条件. 文献[15]讨论了非连通图C4m-1∪C12m-8∪G的优美性,给出了非连通图C4m-1∪C12m-8∪G是优美图的一个充分条件:对任意正整数m(m≥2),如果图G是特征为k且缺标号值k+6m-3的交错图(6m-3≤k+6m-3≤|E(G)|),那么非连通图C4m-1∪C12m-8∪G存在缺标号值k+1的优美标号.本文继续讨论了非连通图C4m-1∪C12m-8∪G的优美性,并给出了非连通图C4m-1∪C12m-8∪G是优美图的几个充分条件.

1相关概念

定义1[1]对于一个图G=(V,E),若存在一个单射θ: V(G)→[ 0,|E(G)|],使得对所有的边e=(u,v)∈E(G),由θ′(e)=|θ(u)-θ(v)|导出的E(G)→[1,|E(G)|]是一个双射,则称G是优美图, θ是G的一组优美标号,称θ′为G的边上的由θ导出的诱导值.

定义2[1]设f为G的一个优美标号,如果存在一个正整数k,使得对任意的uv∈E(G),有

成立,则称f为G的平衡标号(或称G有平衡标号f),且称k为f的特征.图G称为平衡二分图(balanced bipartite graph).

显然,若f为G的平衡标号,则k是边导出标号为1的边的两个端点中标号较小的顶点的标号.

定义4[3-4]V(G)= {u1,u2,…,un}的每个顶点ui都粘接了ri(ri为自然数,i=1,2,…,n)条悬挂边所得到的图,称为图G的(r1,r2,…,rn)-冠,简记为G(r1,r2,…,rn). 特别地,当r1=r2=…=rn=r时,称为图G的r-冠.图G的0-冠就是图G.

2主要结果及其证明

定理1对任意正整数m(m≥2),如果图G是特征为k且缺标号值k+6m-4的交错图(6m-4≤k+6m-4≤|E(G)|),那么非连通图C4m-1∪C12m-8∪G存在缺标号值k+16m-9的优美标号.

定义C4m-1∪C12m-8∪G的顶点标号θ为

θ(x2i)=6m+i+k-3(i=1,2,…,2m-1);

θ(x2i-1)=10m-i+k-4(i=1,2,…,m);

θ(x2m+1)=3m+k-1;

θ(x2i-1)=10m-i+k-3

(i=m+2,m+3,…,2m);

θ(y2i-1)=16m-9-i+k(i=1,2,…,6m-5);

θ(y12m-9)=k+22m-13;

下面证明θ是非连通图C4m-1∪C12m-8∪G的优美标号.

(1) θ:X→[0, k]是单射; θ:Y→[k+16m-8,q+16m-9]-{k+22m-13}是单射;

θ:V(C4m-1)→[k+6m-2,10m-5+k]∪{3m+k-1}是单射;

θ:V(C12m-8)→[k+1,6m-3+k]∪

[10m-4+k,16m-10+k]∪{22m-13+k}-{3m+k-1}是单射.

因而,映射θ′:E(C4m-1∪C12m-8∪G)→[1, q+16m-9]是一一对应的.

由(1)和(2)可知,θ就是非连通图C4m-1∪C12m-8∪G的缺标号值k+16m-9的优美标号.

定理2对任意正整数m,如果图G是特征为k且缺标号值k+2,k+3,…,k+16m-7的交错图(k+16m-7≤|E(G)|),那么非连通图C4m-1∪C12m-8∪G存在缺标号值k+1,k+2,…,k+16m-9的优美标号.

定义C4m-1∪C12m-8∪G的顶点标号θ为

下面证明θ是非连通图C4m-1∪C12m-8∪G的优美标号.

(1) θ:X→[0, k]是单射; θ:Y→[k+16m-8,q+16m-9]-[k+16m-7,k+32m-16]是单射;

θ:V(G)→[-[k+16m-7,k+32m-16]]是单射.

因而,映射θ: V(C4m-1∪C12m-8∪G)→[0, q+16m-9]-[k+1,k+16m-9]是单射.

(2) θ′:E(C4m-1∪C12m-8)→[1,16m-9]是双射;

θ′:E(G)→[16m-8,q+16m-9]是双射.

因而,映射θ′:E(C4m-1∪C12m-8∪G)→[1, q+16m-9]是一一对应的.

由(1)和(2)可知,θ就是非连通图C4m-1∪C12m-8∪G的缺标号值k+1,k+2,…,k+16m-9的优美标号.

引理1[3]对任意正整数m,任意自然数r1,r2,…,rm,C4m(r1,0,r2,0,…,rm,0,…,0)存在特征为2m-1且缺3m的交错标号.

注意到3m=(2m-1)+m+1,由定理1和引理1有如下结论.

推论1对任意正整数m,任意自然数r1,r2,…,r6m-5,非连通图C4m-1∪C12m-8∪C24m-20(r1,0,r2,0,…,r6m-5,0,…,0)存在缺标号值28m-20的优美标号.

例1当m=2,ri=0(i=1,2,…,7)时,由推论1,非连通图C7∪C16∪C28存在缺标号值36的优美标号为

C7:28,23,27,24,18,25,26;

C16:35,14,34,15,33,16,32,17,31,19,30,20,29,21,44,22;

C28:0,51,1,50,2,49,3,48,4,47,5,46,6,45,7,43,8,42,9,41,10,40,11,39,12,38,13,37.

当m=2,ri=i(i=1,2,…,7)时,由推论1,非连通图C7∪C16∪C28(1,0,2,0,3,0,4,0,5,0,6,0,7,0,0,…,0)存在缺标号值36的优美标号为

C7:28,23,27,24,18,25,26;

C16:35,14,34,15,33,16,32,17,31,19,30,20,29,21,44,22;

C28(1,0,2,0,3,0,4,0,5,0,6,0,7,0,0,…,0):0(79),78,1(77,76),75,2(74,73,72),71,3(70,69,68,67),66,4(65,64,63,62,61),60,5(59,58,57,56,55,54),53,6(52,51,50,49,48,47,46),45,7,43,8,42,9,41,10,40,11,39,12,38,13,37.

引理2[3]对任意正整数m,任意自然数r,C4m(r,r,…,r)存在特征为2m(r+1)-1且缺3m(r+1)的交错标号.

注意到3m(r+1)=[2m(r+1)-1]+m(r+1)+1,由定理1和引理2有如下结论.

推论2对任意正整数m,n,任意自然数r,当6m-5=n(r+1)时,非连通图C4m-1∪C12m-8∪C4n(r,r,…,r)存在缺标号值28m-20的优美标号.

例2当m=2,n=1,r=6时, 由推论2,非连通图C7∪C16∪C4(6,6,6,6)存在缺标号值36的优美标号为

C7:28,23,27,24,18,25,26;

C16:35,14,34,15,33,16,32,17,31,19,30,20,29,21,44,22;

C4(6,6,6,6):0(51,50,49,48,47,46),45(1,2,3,4,5,6),7(43,42,41,40,39,38),37(8,9,10,11,12,13).

引理3[1]对任意自然数m,n(m≥2,n≥2),完备二分图Km,n存在特征为m-1且缺m+1,m+2,…,2m-1的交错标号.

注意到m+1=(m-1)+2,m+2=(m-1)+3,…,2m-1=(m-1)+m,由定理1和引理3有如下结论.

推论3对任意自然数h,m,n,当h≥2,m≥6h-4,n≥2时,非连通图C4h-1∪C12h-8∪Km,n存在缺标号值m+16h-10的优美标号.

例3当h=2,m=9,n=3时, 由推论3,非连通图C7∪C16∪K9,3存在缺标号值31的优美标号如图1所示.

图1　非连通图C7∪C16∪K9,3的优美标号

由定理2和引理3有如下结论.

推论4对任意自然数h,m,n,当h≥1,m≥16h-7,n≥2时,非连通图C4h-1∪C12h-8∪Km,n存在缺标号值m,m+1,…,m+16h-10的优美标号.

例4当h=1,m=9,n=3时, 由推论4,非连通图C3∪C4∪K9,3存在缺标号值9,10,…,15的优美标号如图2所示.

图2　非连通图(C3∪C4)∪K9,3的第二种优美标号

引理4[10]对任意自然数n,当n≥2时,C2n+1是有2n+1个顶点的圈,Gn-1是边数为n-1的优美图,则非连通图C2n+1∪Gn-1是优美的.

由文献[12]知,C4m-1∪C12m-8是优美图,且|E(C4m-1∪C12m-8)|=16m-9,由引理4有如下结论.

推论5对任意正整数m,非连通图C4m-1∪C12m-8∪C2(16m-8)+1是优美的.

由推论1知, C4m-1∪C12m-8∪C24m-16是优美图,且|E(C4m-1∪C12m-8∪C24m-16)|=40m-25,由引理4有如下结论.

推论6对任意正整数m,非连通图C4m-1∪C12m-8∪C24m-16∪C2(40m-24)+1是优美的.

3结语

本文研究了非连通图C4m-1∪C12m-8∪G的优美标号,给出了非连通图C4m-1∪C12m-8∪G是优美图的又一个充分条件,可为继续研究非连通图Cm1∪Cm2∪…∪Cmn∪G的优美性提供借鉴.

参考文献:

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

(Ma Kejie. Graceful Graph[M]. Beijing:Beijing University Press, 1991:1-247.)

[ 2 ] 路线,潘伟,李秀芬. 图St(m)∪Kp,q的k优美性及算术性[J]. 吉林大学学报:理学版, 2004,42(3):333-336.

(Lu Xian, Pan Wei, Li Xiufen.k-Gracefulness and Arithmetic of GraphSt(m) ∪Kp,q[J]. Journal of Jilin University:Science Edition, 2004,42(3):333-336.)

[ 3 ] 吴跃生. 关于圈C4h的(r1,r2,…,r4h)-冠的优美性[J]. 华东交通大学学报, 2011,28(1):77-80.

(Wu Yuesheng. On the Gracefulness of the (r1,r2,…,r4h)-Corona of the CycleC4h[J]. Journal of East China Jiaotong University, 2011,28(1):77-80.)

[ 4 ] 吴跃生,李咏秋. 关于圈C4h+3的(r1,r2,…,r4h+3)-冠的优美性[J]. 吉首大学学报:自然科学版, 2011,32(6):1-4.

(Wu Yuesheng ,Li Yongqiu. On the Gracefulness of the (r1,r2,…,r4h+3)-Corona of the CycleC4h+3[J]. Journal of Jishou University:Natural Science Edition, 2011,32(6):1-4.)

[ 7 ] 吴跃生. 图C7(r1,r2,r3,r4,r5,0,0)∪St(m)的优美性[J]. 吉首大学学报:自然科学版, 2012,33(5):9-11.

(Wu Yuesheng. on the Gracefulness of the GraphC7(r1,r2,r3,r4,r5,0,0)∪St(m)[J]. Journal of Jishou University: Natural Science Edition, 2012,33(5):9-11.)

[ 8 ] 吴跃生,王广富,徐保根. 关于C4h+1⊙K1的(Gr1,Gr2,…,Gr4h+1,Gr4h+2)-冠的优美性[J]. 山东大学学报:自然科学版, 2013,48(4):25-27.

(Wu Yuesheng,Wang Guangfu, Xu Baogen. The Gracefulness of the (Gr1,Gr2,…,Gr4h+1,Gr4h+2)-Corona of the GraphC4h+1⊙K1[J]. Journal of Shandong University:Natural Science, 2013,48(4):25-27.)

[ 9 ] 吴跃生. 关于圈C4h+3的(Gr1,Gr2,…,Gr4h+3)-冠的优美性[J]. 吉首大学学报:自然科学版, 2013,34(4):4-9.

(Wu Yuesheng. On the Gracefulness of the (Gr1,Gr2,…,Gr4h+3)-Corona of the GraphC4h+3[J]. Journal of Jishou University:Natural Science Edition, 2013,34(4):4-9.)

[10] 吴跃生,王广富,徐保根. 非连通图C2n+1∪Gn-1的优美性[J].华东交通大学学报, 2012,29(6):26-29.

(Wu Yuesheng,Wang Guangfu, Xu Baogen. The Gracefulness of the Unconnected GraphC2n+1∪Gn-1[J]. Journal of East China Jiaotong University, 2012,29(6):26-29.)

[11] Gallian J A. A Dynamic Survey of Graph Labeling[J]. The Electronic Journal of Combinatorics, 2009,16:1-308.

[12] 吴跃生. 非连通图C4m-1∪G的优美标号[J].吉首大学学报:自然科学版, 2014,35(3):1-3.

(Wu Yuesheng. Graceful Labeling of the Unconnected GraphC4m-1∪G[J]. Journal of Jishou University: Natural Science Edition, 2014,35(3):1-3.)

[13] 吴跃生. 非连通图G+e∪Hk-1的优美性[J]. 吉首大学学报:自然科学版, 2014,35(2):3-5.

(Wu Yuesheng. Gracefulness of the Unconnected GraphG+e∪Hk-1[J]. Journal of Jishou University: Natural Science Edition, 2014,35(2):3-5.)

[14] 贾慧羡,左大伟. 与扇图相关的2类图的超边优美标号[J]. 吉首大学学报:自然科学版, 2014,35(2):6-9.

(Jia Huixian, Zuo Dawei. Super-Edge-Graceful Labelings of Two Kinds of Graphs Associated with the Fan Graph[J]. Journal of Jishou University: Natural Science Edition, 2014,35(2):6-9.)

[15] 吴跃生. 非连通图C4m-1∪C12m-8∪G的优美标号[J]. 沈阳大学学报:自然科学版, 2014,26(4):334-337.

【责任编辑: 王颖】

(Wu Yuesheng. Graceful Labeling of Unconnected GraphC4m-1∪C12m-8∪G[J]. Journal of Shenyang University:Natural Science, 2014,26(4):334-337.)

Further Discussion on Graceful Labeling of Unconnected GraphC4m-1∪C12m-8∪G

WuYuesheng

(School of Basic Science, East China Jiaotong University, Nanchang 330013, China)

Abstract:The gracefulness of the unconnected graphC4∪C12∪Gis discussed. It is proved that for any positive integerm, whenGis alternating graph (6m-4≤k+6m-4≤|E(G)|) that characterized bykand lack of label values ofk+6m-4, the unconnected graphC4∪C12∪Ghas graceful labeling which lack of lable values ofk+16m-9, wherein,Cspanis a cycle withmvertices.

Key words:graceful graph; balanced bipartite graph; unconnected graph; graceful labeling

收稿日期:2014-05-24

中图分类号:O 157.5

文献标志码:A

作者简介:吴跃生(1959-),男,江西瑞金人,华东交通大学副教授,硕士.

基金项目:国家自然科学基金资助项目(11261019,11361024); 江西省教育厅2014年度科学技术研究项目(GJJ14380).

文章编号:2095-5456(2015)01-0072-05