非连通图(P2∨)(r1，r2，…，rn+2)∪Gr的优美性

吴跃生，王广富，徐保根

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

非连通图(P2∨)(r1，r2，…，rn+2)∪Gr的优美性

吴跃生，王广富，徐保根

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

优美图；联图；非连通图；冠

1 预备知识

图的标号问题是组合数学中一个热门课题.[1-12]它不仅属于图论领域，也属于设计理论的范畴，主要应用于编码设计、变压器箱设计、雷达脉冲、射电天文学、通讯网络、晶体结构中原子位置的测定和导弹控制码等研究.

本文所讨论的图均为无向简单图，V(G)和E(G)分别表示图G的顶点集和边集.为了简单起见，我们把一个有p个顶点q条边的图记为(p，q)-图.记号[m，n]表示整数集合{m，m+1，m+2，…，n}，其中m和n均为非负整数，且满足0≤m

定义1[1]对于一个图G=(V，E)，如果存在一个单射θ：V(G)→{0，1，2，…，|E(G)|}，使得对所有边e=(u，v)∈E(G)，由θ′(e)=|θ(u)-θ(v)|导出的E(G)→{1，2，…，|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的对偶二分点.

定义5v1和v2是图G的两个不相邻的顶点，连接v1和v2，使图G增加一条边，所得到的图，称为图G(v1，v2).

定义6[5-6]V(G)={v1，v2，…，vn}中的每个顶点vi都粘接了ri条悬挂边(ri为自然数，i=1，2，…，n)所得到的图，称为图G的(r1，r2，…，rn)-冠，简记为G(r1，r2，…，rn).特别的，当r1=r2=…=rn=r时，称为图G的r-冠.图G的0-冠就是图G.

顶点y1粘接了r1条悬挂边，顶点y2粘接了r2条悬挂边，顶点xi粘接了r2+i条悬挂边.

2 主要结果及其证明

再令θ3(v)=q-θ2(v)，v∈V(G)，则θ，θ1，θ2，θ3是图G的互不相同的4种平衡标号，其特征分别为k，q-k-1，k，q-k-1.

引理2 当k≥2时，(p，q)-图G是特征为k的平衡二分图，Hk-1是边数为k-1的优美图，则非连通图G+e∪Hk-1是优美的.

证明 设V(G)划分成两个集合X，Y；v1，v2∈X，θ是图G的平衡标号，且θ(v1)=0，θ(v2)=k，即v2是平衡二分图G的二分点，e=v1v2.

下面证明标号θ1是图G+e∪Hk-1的优美标号.

θ1：V(G+e∪Hk-1)=V(G)∪V(Hk-1)→[0，q+k]

是一个单(或双)射.

因此θ1是图G+e∪Hk-1的优美标号.证毕.

引理3 对任意自然数

m≥2，n≥2，ri(i=1，2，…，m+1，m+n)，km，n(r1，r2，…，rm+1，0，0，…，rm+n)

是平衡二分图(交错图).

证明 设V(Km，n)={x1，x2，…，xm，y1，y2，…，yn}，与xi邻接的端点(或叶)记为xi，j，i=1，2，…，m；j=1，2，…，ri.与y1邻接的端点(或叶)记为y1，j，j=1，2，…，rm+1.与yn邻接的端点(或叶)记为yn，j，j=1，2，…，rm+n.图Km，n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠如图1所示.

定义图的(r1，r2，…，rm+1，0，0，…，rm+n)-冠的顶点标号θ为：

θ(y1，i)=i-1，i=1，2，…，rm+1.

当rm+1=0时，

θ(y1，i)=θ(y1)；

θ(xi)=θ(y1，rm+1)+i=rm+1-1+i，i=1，2，…，m；

θ(yi)=θ(y1)-(i-1)m，i=2，…，n-1；

当ri=0时，

θ(xi，j)=θ(xi)；

θ(yn)=θ(x1，1)-1=rm+1+rm+n+m；

θ(yn，j)=θ(xm)+j，j=1，2，…，rm+n.

当rm+n=0时，

θ(yn，j)=θ(yn).

图1 Km，n的(r1，r2，…，rm+1，0，0，…，rm+n)-冠

图2 K5，3的(1，2，3，4，5，6，0，7)-冠的平衡标号

下面证明标号θ是图Km，n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠的优美标号.

(1) 由于

0=θ(y1，1)<θ(y1，2)<…<θ(y1，rm+1)<θ(x1)<θ(x2)<…<
θ(xm)<θ(yn，1)<θ(yn，2)<…<θ(yn，rm+n-1)<θ(yn，rm+n)<θ(yn)<
θ(x1，1)<θ(x1，2)<…<θ(x1，r1)<θ(x2，1)<θ(x2，2)<…<θ(x2，r1)<
θ(x3，1)<θ(x3，2)<…<θ(x3，3)<…<θ(xm，1)<θ(xm，2)<…<θ(xm，rm)<
θ(yn-1)<θ(yn-2)<…<θ(y1)=|E|.

容易验证V(Km，n(r1，r2，…，rm+1，0，0，…，0，rm+n))→{0，1，2，…，|E|}是一个单射.

(2) 由点标号θ导出的边标号θ′为：

θ′(y1y1，i)=|E|+1-i，i=1，2，…，rm+1.

θ′(y1xi)=|E|-rm+1+1-i，i=1，2，…，m.

θ′(yixj)=|E|-(i-1)m-rm+1+1-j，i=2，…，n-1；j=1，2，…，m.

θ′(ynxi)=m+1+rm+n-i，i=1，2，…，m.

由于

1=θ′(ynyn，1)<θ′(ynyn，2)<…<θ′(ynyn，rm+n)<θ′(ynxm)<θ′(ynxm-1)<…<
θ′(ynx1)<θ′(x1x1，1)<θ′(x1x1，2)<…<θ′(x1x1，r1)<θ′(x2x2，1)<θ′(x2x2，2)<…<
θ′(x2x2，r2)<…<θ′(xmxm，1)<θ′(xmxm，2)<…<θ′(xmxm，rm)<θ′(xmyn-1)<
θ′(xm-1xn-1)<…<θ′(x1yn-1)<θ′(xmyn-2)<θ′(xm-1yn-2)<…<θ′(x1yn-2)<…<
θ′(xmy1)<θ′(xm-1y1)<θ′(x1y1)<θ′(y1y1，rm+1)<θ′(y1y1，rm+1-1)<…<θ′(y1y1，2)=|E|.

容易验证θ′：E(Km，n(r1，r2，…，rm+1，0，0，…，0，rm+n))→{0，1，2，…，|E|}是一个双射.因此θ是图Km，n的(r1，r2，…，rm+1，0，0，…，rm+n)-冠的优美标号.

令

X={y1，1，y1，2，…，y1，rm+1，x1，x2，xm，yn，1，yn，2，…，yn，rm+n}，

Y=V(Km，n(r1，r2，…，rm+1，0，0，…，0，rm+n))-X，

有

故图Km，n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠是平衡二分图(交错图)，且图Km+n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠关于平衡标号θ的特征为rm+1+rm+n+m-1.证毕.

图K5，3的(1，2，3，4，5，6，0，7)的平衡标号如图2所示.

引理4 对任意自然数m≥2，ri(i=1，2，…，m+2)，Km，2(r1，r2，…，rm+2)是平衡二分图(交错图)，且Km，2(r1，r2，…，rm+2)关于平衡标号θ的特征为rm+1+rm+2+m-1.

图K5，2(1，2，3，4，5，6，7)的两种平衡标号如图3—4所示.

图3 K5，2(1，2，3，5，6，7)的第一种平衡标号

图4 K5，2的(1，2，3，4，5，6，7)的第二种平衡标号

证明 设θ1是引理4所给出的图Kn，2(r1，r2，…，rn+2)的平衡标号(如图3)，图Kn，2(r1，r2，…，rn+2)的顶点集如图1所示，则有图Kn，2(r1，r2，…，rn+2)关于平衡标号θ1的特征为

rn+1+rn+2+n-1，θ1(y1)=|E(Kn，2(r1，r2，…，rn+2))|，θ1(y2)=rn+1+rn+2+n，

即顶点y2是图Kn，2(r1，r2，…，rn+2)关于平衡标号θ1的对偶二分点.令

θ2=|E(Kn，2(r1，r2，…，rn+2))|-θ1，

由引理1可知，θ2是图Kn，2(r1，r2，…，rn+2)的另一种平衡标号(如图4)，则有图Kn，2(r1，r2，…，rn+2)关于平衡标号θ2的特征为

即顶点y2是图kn，2(r1，r2，…，rn+2)关于平衡标号θ2的二分点.由引理2可知，

在定理1中，令ri=0，i=1，2，…，n+2，有如下的结论：

图5 图的优美标号

图6 图的优美标号

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

[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)-冠的优美性[J].吉首大学学报：自然科学版，2011，32(6)：1-4.

[8] 魏丽侠，张昆龙.几类并图的优美标号[J].中山大学学报：自然科学版，2008，47(3)：10-13.

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

[10] 张家娟，郭珠霞，周向前，等.优美图的一些性质[J].数学的实践与认识，2012，42(13)：197-201.

[11] 张志尚，黄文强，东恺.两类并图的优美标号[J].东北师大学报：自然科学版，2013，45(2)：30-34.

[12] GALLIAN J A.A dynamic survey of graph labeling[J].The Electronic Journal of Combinatorics，2013，16(DS6)：1-308.

Keywords:graceful graph；join graph；disconnected graph；corona

(责任编辑：陶 理)

WU Yue-sheng，WANG Guang-fu，XU bao-gen

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

1000-1832(2014)03-0038-05

10.11672/dbsdzk2014-03-008

2013-01-05

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

吴跃生(1959—)，男，硕士，副教授，主要从事图论研究.

O 157.5 [学科代码] 110·7470

A