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

2014-07-27吴跃生王广富徐保根

东北师大学报（自然科学版） 2014年3期

关键词：标号端点顶点

吴跃生，王广富，徐保根

(华东交通大学理学院，江西南昌 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，

有