非连通图2C4m∪G的优美标号

吴跃生,王广富,徐保根

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

1 引言与概念

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

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

文献[1]已经证明: 非连通图2C4m是优美图．

本文讨论了非连通图2C4m∪G的优美性．

定义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(u)>k≥f(v)或f(u)≤k

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

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

定义3[1]在平衡二分图G中,设其优美标号θ的特征为k,并且θ(u0)=k,θ(v0)=k+1,则称u0为G的二分点,v0为G的对偶二分点．

2 主要结果及其证明

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

定义2C4m∪G的顶点标号θ为

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

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

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

θ(y2i-1)=8m-i+k+1,i=1,2,…,2m-1;θ(y4m-1)=k+10m+1;

下面证明θ是非连通图2C4m∪G的优美标号．

(1)

θ:X→[0,k]是单射(或双射);θ:Y→[k+8m+1,q+8m]{k+10m+1}是单射(或双射);

θ:V(2C4m∪G)→[0,q+8m]{k+1}是单射．

(2)

θ′(x2m-1x2m)=4m,

θ′(x2mx2m+1)=4m-1,

θ′(x4mx1)=2m,

θ′(y4m-1y4m)=8m-1,

θ′(y4m-2y4m-1)=8m,

θ′(y4my1)=6m-2,

θ′:E(G)→[8m+1,q+8m]是双射;

θ′:E(2C4m∪G)→[1,q+8m]是一一对应．

由(1)和(2)可知θ就是非连通图2C4m∪G的缺k+1标号值的优美标号．

令X1=X∪{x2i,i=1,2,…,2m}∪{y2i,i=1,2,…,2m},

Y1=Y∪{x2i-1,i=1,2,…,2m}∪{y2i-1,i=1,2,…,2m},

所以,θ就是非连通图C4m∪G的特征为4m+k+1,且缺k+1标号值的交错标号． 证毕．

引理1 对任意正整数n,设C4n是有4n个顶点的圈,则C4n存在特征为2n-1,且缺3n的交错标号．

证明记圈C4n上的顶点依次为v1,v2,…,v4n,定义圈C4n的顶点标号θ为

θ(v2i-1)=i-1,i=1,2,…,2n.

容易验证,θ就是圈C4n的特征为2n-1,且缺3n的交错标号．

注意到:3n=(2n-1)+n+1,由定理和引理1得推论1.

推论1 对任意正整数m,非连通图2C4m∪C8m存在特征为8m且缺4m标号值的交错标号．

例1 由推论1给出的非连通图2C8∪C16的特征为16且缺8标号值的交错标号为

20,14,19,11,18,15,17,16;

23,9,22,10,21,12,28,13;

0,32,1,31,2,30,3,29,4,27,5,26,6,25,7,24．

引理2[1]如果θ是图G特征为k的交错标号,令θ1(v)=|E(G)|-θ(v),v∈V(G),则θ1是图G特征为|E(G)|-k-1的交错标号．

由推论1和引理2得推论2.

推论2 对任意正整数m,非连通图2C4m∪C8m存在特征为8m-1且缺12m标号值的交错标号．

注意到:12m=(8m-1)+4m+1,由定理和推论2得推论3.

推论3 对任意正整数m,非连通图2C8m∪(2C4m∪C8m)存在特征为16m且缺8m标号值的交错标号．

例2 由推论3给出的非连通图2C16∪(2C8∪C16)的特征为32且缺16标号值的交错标号为:

9,55,10,54,11,52,4,51;

12,50,13,53,14,49,15,48;

64,0,63,1,62,2,61,3,60,5,59,6,58,7,57,8;

40,26,39,27,38,28,37,21,36,29,35,30,34,31,33,32;

47,17,46,18,45,19,44,20,43,22,42,23,41,24,56,25.

由推论3和引理2得推论4.

推论4 对任意正整数m,非连通图2C8m∪(2C4m∪C8m)存在特征为16m-1且缺24m标号值的交错标号．

注意到:24m=(16m-1)+8m+1,由定理和推论4得推论5.

推论5 对任意正整数m,非连通图2C16m∪(2C8m∪(2C4m∪C8m))存在特征为32m且缺16m标号值的交错标号．

由推论5和引理2得推论6.

推论6 对任意正整数m,非连通图2C16m∪(2C8m∪(2C4m∪C8m))存在特征为32m-1且缺48m标号值的交错标号．

……

重复上述过程,可以构造出许多交错图．

参考文献:

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

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

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

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

[5] 吴跃生.关于图P6k+53∪Pn3的优美性[J].吉首大学学报:自然科学版,2012,33(3):4-7.

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

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

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

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

[11] Gallian J A A. Dynamic survey of graph labeling[J]. The Electronic Journal of Combinatorics,2013,16(6): 1-308.

[12] Golom B S W. How to Number of a Graph:Graph Theory and Computing[M].New York:Academic Press,1972.

[13] Gallian A. A guide to the graph labeling zoo[J].Discrete Mathematics,1994,49:213-229.

[14] Kathie San Km.Two classes of graceful graphs[J].Ars Combinatioria,2000,55:129-132.

[15] Frank Hsu D. Harmonious labelings of windmill graphs and related graphs[J]. Journal of Graph Theory,1982,6(1):85-87.