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

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

吴跃生

(华东交通大学基础科学学院,江西 南昌 330013)

摘要：讨论了非连通图C4m-1∪G的优美性，给出了非连通图C4m-1∪G是优美图的2个充分条件.

关键词：优美图;交错图；非连通图;优美标号

文章编号：1007-2985(2015)01-0001-04

中图分类号：O157.5文献标志码：A

DOI:10.3969/j.issn.1007-2985.2015.01.001

收稿日期：*2014-05-27

基金项目：国家自然科学基金资助项目(11261019,11361024)；江西省自然科学基金资助项目(20114BAB201010)

作者简介：吴跃生(1959—)，男，江西瑞金人，华东交通大学基础科学学院副教授，硕士，主要从事图论研究.

1相关定义

图的优美标号问题是组合数学中一个热门课题[1-15].

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

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

文献[12]中讨论了非连通图C4m-1∪G的优美性，给出了非连通图C4m-1∪G是优美图的2个充分条件：对任意正整数m，若图G是特征为k且缺k+3m-1标号值的交错图(3m-1≤k+3m-1≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+1的优美标号；对任意正整数m，若图G是特征为k且缺k+m+1标号值的交错图(m+1≤k+m+1≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+1的优美标号.文献[13]中讨论了非连通图D2,8∪G的优美性.

笔者继续讨论非连通图C4m-1∪G的优美性.

定义2设f为G的一个优美标号，若存在一个正整数k，使得对∀uv∈E(G)有f(u)>k≥f(v)或f(u)≤k

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

2主要结果及其证明

定理1对任意正整数m，若图G是特征为k且缺k+3m-2标号值的交错图(3m-2≤k+3m-2≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+4m-1的优美标号.

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

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

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

(ⅰ)θ:X→[0,k]是单射(或双射);θ:Y→[k+4m,q+4m-1]-{7m-3+k}是单射(或双射);θ:V(C4m-1)→[k+1,k+4m-2]∪{7m-3+k}是单射(或双射);θ：V(C4m-1∪G)→[0,q+4m-]-{k+4m-1}是单射.

(ⅱ)

θ′(x 2m+2x 2m+1)=4m-1；

θ′(x2mx2m+1)=4m-2；θ′(x4m-1x1)=2m-2.

θ′:E(C4m-1)→[1,4m-1]是双射；θ′：E(G)→[4m,q+4m-1]是双射.θ′：E(C4m-1∪G)→[1,q+4m-1]是一一对应.

由(ⅰ)和(ⅱ)可知，θ就是非连通图C4m-1∪G的缺k+4m-1标号值的优美标号.证毕.

定理2对任意正整数m，若图G是特征为k且缺k+m标号值的交错图(m≤k+m≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+4m-1的优美标号.

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

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

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

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

(ⅰ)θ:X→[0,k]是单射(或双射);θ:Y→[k+4m,q+4m-1]-{k+5m-1}是单射(或双射);θ:V(C4m-1)→[k+1,k+4m-2]∪{k+5m-1}是单射(或双射);θ：V(C4m-1∪G)→[0,q+4m-1]-{k+4m-1}是单射.

(ⅱ)

θ′(x 2m-1x 2m)=4m-1；

θ′(x2mx2m+1)=4m-2；θ′(x4m-1x1)=2m-1.

由(ⅰ)和(ⅱ)可知θ就是非连通图C4m-1∪G的缺k+4m-1标号值的优美标号.证毕.

定义4[4-7]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.

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

注意到3m=(2m-1)+m+1，由定理1和引理1有以下结论：

推论1对任意正整数m(m≥2)，任意自然数r1,r2,…,r3m-3，非连通图C4m-1∪C12m-12(r1,0,r2,0,…,r3m-3,0,…,0)存在缺标号值10m-8的优美标号.

例1当m=2，r1=r2=r3=0时，由推论1给出的非连通图C7∪C12存在缺标号值12的优美标号为:

C7:6,11,7,10,16,9,8;

C12:0,19,1,18,2,17,3,15,4,14,5,13.

当m=2，r1=1,r2=2,r3=3时，由推论1给出的非连通图C7∪C12(1,0,2,0,3,0,0,…,0)存在缺标号值12的优美标号为：

C7:6,11,7,10,16,9,8;

C12(1,0,2,0,3,0,0,…,0):0(25),24,1(23,22),21,2(20,19,18),17,3,15,4,14,5,13.

由定理2和引理1有以下结论：

推论2对任意正整数m，任意自然数r1,r2,…,rm-1,非连通图C4m-1∪C4m-4(r1,0,r2,0,…,rm-1,0,…,0)存在缺6m-4标号值的优美标号.

例2当m=3，r1=r2=0时，由推论2给出的非连通图C11∪C8的缺标号值14的优美标号为：

C11:4,13,5,12,6,17,7,11,8,10,9;

C8：0,19,1,18,2,16,3,15.

当m=3，r1=8,r2=9时，由推论2给出的非连通图C11∪C8(8,0,9,0,0,0,0,0)的缺标号值14的优美标号为：

C11:4,13,5,12,6,17,7,11,8,10,9;

C8(8,0,9,0,0,0,0,0):0(36,35,34,33,32,31,30,29),28,1(27,26,25,24,23,22,21,20,19),18,2,16,3,15.

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

因为E(C4m-1)=4m-1，所以由引理2有以下结论：

推论3设m为任意的正整数，则非连通图C4m-1∪C2(4m)+1是优美的.

因为E(C4m-1∪C12m-12(r1,0,r2,0,…,r3m-3))=16m-13+r1+r2+…+r3m-3，令16m-13+r1+r2+…+r3m-3=a,所以由推论1和引理2有以下结论：

推论4对任意正整数m(m≥2)，任意自然数r1,r2,…,r3m-3，非连通图C4m-1∪C12m-12(r1,0,r2,0,…,r3m-3,0,…,0)∪C2(a+1)+1是优美的.

因为E(C4m-1∪C4m-4(r1,0,r2,0,…,rm-1))=8m-5+r1+r2+…+rm-1，令8m-5+r1+r2+…+rm-1=b,所以由推论2和引理2有以下结论：

推论5对任意正整数m(m≥2)和任意自然数r1,r2,…,rm-1，非连通图C4m-1∪C4m-4(r1,0,r2,0,…,rm-1,0,…,0)∪C2(b+1)+1是优美的.

参考文献：

[1]马克杰.优美图.北京:北京大学出版社，1991.

[2]杨显文.关于C4m蛇的优美性.工程数学学报，1995,12(4):108-112.

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

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

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

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

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

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

[11] GALLIAN J A.A Dynamic Survey of Graph Labeling.The Electronic Joumal of Combinatorics，2013,16(DS6)：1-308.

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

[13] 吴跃生.非连通图D2,8∪G的优美性.西华师范大学学报：自然科学版,2014:35(1):4-6.

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

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

Revisiting the Graceful Labeling of the Unconnected GraphC4m-1∪G

WU Yuesheng

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

Abstract:The gracefulness of the unconnected graph C4m-1∪G is discussed.Two sufficient conditions are given for the gracefulness of unconnected graph C4m-1∪G.

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

(责任编辑向阳洁)