图Fn,4(r1,r2,…,r3n+1)的交错标号*

吴跃生

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

图Fn,4(r1,r2,…,r3n+1)的交错标号*

吴跃生

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

对任意正整数n，对任意自然数ri,i=1,2,…,3n+1，V(Fn,4)={v1,v2,…,v3n+1}，图Fn,4(r1,r2,…,r3n+1)表示V(Fn,4)中的vi都粘接了ri条悬挂边所得到的图。讨论了图Fn,4(r1,r2,…,r3n+1)的优美性。证明了：对任意正整数n，对任意自然数，i=1,2,…,3n+1，图Fn,4(r1,r2,…,r3n+1)是交错图。

优美图；交错图；优美标号；交错标号

图的优美标号问题是图论中一个富有挑战性的课题[1-17]。马克杰猜想：任意优美图的r-冠是优美图。这一猜想至今未被证明或否定。本文把顺序有一个公共顶点的n个4个顶点的圈C4所形成的图记为Fn,4(如图1所示)。

图1 图Fn,4Fig.1 Graph Fn,4

图Fn,4是优美图[1]。文[1]已经证明：如果树T是优美图，则树T的r-冠是优美图；文[1]证明：设Pn是有n个顶点的路，则P1∨Pn的r-冠是优美图；文[2-3]证明: 圈C4m-1和圈C4m的r-冠都是优美图；文[1]也证明：完备二分图Km,n的冠I(Km,n)是优美的。文[5]证明：I(∧Cn,4)和I(Fn,4)都是优美的。文[6]证明：I(1-Fm,4)和I(K1,1,1,n)都是优美的。本文将证明图Fn,4(r1,r2,…,r3n+1)是交错图和图Fn,4的r-冠是交错图。

1 概 念

定义1[2-3]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, 图G的1-冠也称为图G的冠，记作I(G)。

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

2 主要结果及其证明

定理1 对任意正整数n，对任意自然数ri,i=1,2,…,3n+1，图Fn,4(r1,r2,…,r3n+1)(如图2所示)是交错图。图Fn,4(r1,r2,…,r3n+1)存在缺r2+1,r2+r3+r5+3,r2+r3+r5+r6+r8+5,r2+r3+r5+r6+r8++r9+r11+7, …,r2+r3+r5+r6+…+r3n-4+r3n-3+r3n-1+2n-1特征值为r2+r3+r5+r6+…+r3n-1+r3n+2n的交错标号。

图2 Fn,4(r1,r2,…,r3n+1)Fig.2 Graph Fn,4(r1,r2,…,r3n+1)

证明 定义Fn,4(r1,r2,…,r3n+1)的顶点标号θ(如图3, 图4)为：

当r2≠0时,θ(x2,i)=θ(u1)+i=i,i=1,2,…,r2; 当r2=0时,x2,i=u2,

当r3≠0时，θ(x3,i)=r2+1+i,i=1,2,…,r3; 当r3=0时,x3,i=u3,θ(u4)=r2+r3+2；

当r3k-2≠0时，θ(u3k)=θ(x3k-2,r3k-2)-1, 当r3k-2=0时,θ(u3k)=θ(u3k-4)-1,

θ(u3k-1)=θ(u3k)-1,k=2,3,…,n

当r3k-1≠0时，θ(x3k-1,i)=θ(u3k-2)+i,k=2,3,…,n,i=1,2,…,r3k-1;当r3k-1=0时,x3k-1,i=u3k-1;

当r3k-1≠0,r3k≠0时,θ(x3k,i)=θ(x3k-1,r3k-1)+1+i,k=2,3,…,n,i=1,2,…,r3k;

当r3k-1=0,r3k≠0时,θ(x3k,i)=u3k-2+1+i,k=2,3,…,n,i=1,2,…,r3k;

当r3k=0时,x3k,i=u3k;

当r3k≠0时,θ(u3k+1)=θ(x3k,r3k)+1,k=2,3,…,n;

当r3k-1≠0,r3k=0时,θ(u3k+1)=θ(x3k-1,r3k-1)+2,k=2,3,…,n;

当r3k-1=0,r3k=0时,θ(u3k+1)=θ(u3k-2)+2,k=2,3,…,n;

当r3k+1≠0时,θ(x3k+1,i)=θ(u3k-1)-i,k=2,3,…,n,i=1,2,…,r3k+1;当r3k+1=0时,x3k+1,i=u3k+1;

图3 图F5，4(1,2,…，16)的交错标号Fig.3 The alternating labeling of F5，4(1,2,…，16)

图4 图F5，4(1,0,2,0,…,8,0)的交错标号Fig.4 The alternating labeling of F5，4(1,0,2,0,…,8,0)

下面证明θ是非连通图Fn,4(r1,r2,…,r3n+1)的交错标号。

(i)

r2+r3+r5+r6+r8+r9+r11+7,…,r2+r3+r5+r6+…+r3n-4+r3n-3+r3n-1+2n-1}是双射。

令

则有

所以，θ就是非连通图Fn,4(r1,r2,…,r3n+1)的特征为r2+r3+r5+r6+…+r3n-1+r3n+2n,且缺r2+1,r2+r3+r5+3,r2+r3+r5+r6+r8+5,r2+r3+r5+r6+r8+r9+r11+7,…,r2+r3+r5+r6+…+r3n-4+r3n-3+r3n-1+2n-1标号值的交错标号。证毕。

在定理1中，令r1=r2=…=r3n+1=0，有

推论1 对任意正整数n, 图Fn,4(如图5)是交错图，图Fn,4存在缺 1,3,…,2n-1，特征值为2n的交错标号。

图5 图F5，4的交错标号Fig.5 The alternating labeling of F5,4

在定理1中，令r1=r2=…=r3n+1=r，有

推论2 对任意正整数n,r,图Fn,4的r-冠是交错图。存在缺r+1,3(r+1),…,(2n-1)(r+1)，特征值为2n(r+1)的交错标号。特别地，当r=1时，I(Fn,4)是交错图(这正是文[2]定理2的结论)，存在缺 2,6,…,2(2n-1),特征值为4n的交错标号。

在定理1中，令r1=r2=r3=r5=r6=…=r3n-1=r3n=r3n+1=1，r4=r7=…=r3n-2=2有

推论3 对任意正整数n,r,图Fn,4(1,1,1,2,1,1,2,1,1,2,…,1,1,2,1,1,1)的是交错图, 存在缺 2,6,…,2(2n-1)，特征值为4n的交错标号(这正是文[5]定理3的结论)。

引理1[3]交错图是k-优美图，交错图是奇(偶)优美图和奇(偶)强协调图。

由定理1和引理1有

推论4 对任意正整数n,对任意自然数ri,i=1,2,…,3n+1，图Fn,4(r1,r2,…,r3n+1)是k-优美图，交错图是奇(偶)优美图和奇(偶)强协调图。

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

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

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

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

[5] 唐保祥，任韩. 3类特殊图的优美性[J]. 武汉大学学报(理学版), 2014, 60(6): 553-556.

[6] 唐保祥，任韩. 2类优美图的冠的优美标号[J]. 中山大学学报(自然科学版), 2015, 54(5): 24-27.

[7] 吴跃生，王广富，徐保根. 交错图的奇优美性和协调性[J]. 武汉大学(理学版)，2014，60(6): 557-560.

[8] GALLIAN J A. A dynamic survey of graph labeling [J]. The Electronic Joumal of Combinatorics, 2013,16, DS6: 1-308.

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

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

[12] 吴跃生. 非连通图C3(m,0,0)∪G的优美性[J]. 华东交通大学学报, 2013, 30(6): 35-39.

[13] 吴跃生. 非连通图L6∪G的优美标号[J] . 西华大学学报(自然科学版), 2015, 34(2): 30-35.

[14] 吴跃生，王广富，徐保根. 非连通图G1∪G2⊙K1的优美性[J]. 江西师范大学学报(自然科学版), 2014, 38(3): 236-239.

[15] 张政，胡红亮. 图ω4g,4h+3的(r1,r2,…,r4g+4h+2)-冠的优美性[J]. 华东交通大学学报, 2014, 31(5): 117-121.

[17] 王涛，王清，李德明. 和轮相关图的优美性[J]. 中山大学学报(自然科学版), 2011, 50(6): 16-19.

The alternating labeling of the graphFn,4(r1,r2,…,r3n+1)

WUYuesheng

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

For natural numbersn(n≥1),r1,r2,…,r3n+1,letV(Fn,4)={v1,v2,…,v3n+1},Fn,4(r1,r2,…,r3n+1)isthenewgraphthateveryvertexviintheV(Fn,4)={v1,v2,…,v3n+1}isbondingrihangingedges.ThegracefulnessofthegraphFn,4(r1,r2,…,r3n+1)isdiscussed.ItisprovedthatthegraphFn,4(r1,r2,…,r3n+1)isalternatinggraph.

graceful graph; alternating graph; graceful labeling; alternating labeling

10.13471/j.cnki.acta.snus.2016.04.002

2016-01-04

国家自然科学基金资助项目(11261019，11361024)

吴跃生(1959年生)，男；研究方向：图论;E-mail:616100567@qq.com

O

A

0529-6579(2016)04-0011-04