一类直径为6的树的优美性

严谦泰

(安阳师范学院数学与统计学院， 河南安阳 455002)

0 引言

优美图的研究始于1963年Ringel的一个猜想[1]和1966年Rosa的一篇论文[2].1972年， Golomb明确给出了优美图的定义[3]， 之后Gnanajoethi又提出了每棵树都是奇优美的[4]， 开始了奇优美图的研究. 但由于缺少系统和有力的工具， 至今只能对一些特殊图类研究其优美性.文献[5-8]分别研究直径为4,5的树的优美性， 本文将其推进一步， 研究一类直径为6的树的优美性.

定义1[2]对于简单图G=[V,E]， 如果存在一个映射f∶V(G)→{0,1,2,…,|E|}， 满足

1)对任意的u,v∈V,若u≠v,则f(u)≠f(v)；

2)max{f(v)|v∈V}=|E|；

3)对任意的e1,e2∈E,若e1≠e2,则

g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv；

4){g(e)|e∈E}={1,2,…,|E|},

则称G为优美图， 称f为G的优美标号.

定义2[3]对于简单图G=[V,E]， 如果存在一个映射f∶V(G)→{0,1,2,…,2|E|-1}， 满足

1)对任意的u,v∈V,若u≠v,则f(u)≠f(v)；

2)max{f(v)|v∈V}=2|E|-1；

3)对任意的e1,e2∈E,若e1≠e2,则

g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv；

4){g(e)|e∈E}={1,3,5,…,2|E|-1},则称G为奇优美图， 称f为G的奇优美标号.

定义3[2]对于简单图G=[V,E]， 如果存在一个映射f∶V(G)→{0,1,2,…,|E|+k-1}， 满足

1)对任意的u,v∈V,若u≠v,则f(u)≠f(v)；

2)max{f(v)|v∈V}=|E|；

3)对任意的e1,e2∈E,若e1≠e2,则

g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv；

4){g(e)|e∈E}={k,k+1,…,k+|E|-1},

则称G为k-优美图， 称f为G的k-优美标号.

定义4[2]对于图G=[V,E]， 称

d(G)=max{d(u,v)|u,v∈V}

为G=[V,E]的直径， 其中d(u,v)表示u,v两点之间的距离.

本文研究一类直径为6的树的优美性， 文中未加说明的术语和符号参见文献[2].

1 主要结论及证明

本文研究如下一类直径为6的树T的优美性.

树T有一个中心点x0， 其半径为3， 且T-x0是两个直径为4的树， 设与x0相邻顶点是x和y， 与x相邻顶点有s个(x0除外)， 设为x1,x2,…,xs， 与y相邻顶点有s个(x0除外)， 设为y1,y2,…,ys， 而每一个xi和yi(i=1,2,…,s)都与t个顶点相邻， 即t片树叶， 分别为xi,1,xi,2,…,xi,t和yi,1,yi,2,…,yi,t，i=1,2,…,s.如果借用根树的说法， 即x0是树根，x0有两个儿子x和y，x有s个儿子x1,x2,…,xs，y有s个儿子y1,y2,…,ys， 而每一个xi和yi(i=1,2,…,s)都有t个儿子， 分别为xi,1,xi,2,…,xi,t和yi,1,yi,2,…,yi,t，i=1,2,…,s.把此类图记为T2,s,t，其中有3+2s+2st个顶点.

定理1当s=2时，T2,2,t是优美图.

证明T2,2,t中有7+4t个顶点， 边数|E|=6+

4t， 给出T2,2,t的顶点标号f如下:

f(x0)=0，f(x)=6+4t=|E|，f(y)=3+4t=

|E|-3；

f(x1)=2，f(x2)=1，f(y1)=5+4t，f(y2)=

4+4t；

f(y11)=3，f(y12)=7,…,f(y1t)=3+4(t-1)；

f(y21)=f(y11)+1，f(y22)=f(y12)+1,…,f(y2t)=f(y1t)+1；

f(x11)=f(y21)+1，f(x12)=f(y22)+1， …,f(x1t)=f(y2t)+1；

f(x21)=f(x11)+1，f(x22)=f(x12)+1， …,f(x2t)=f(x1t)+1.

可以验证这是一个优美标号.

定理2当s=3时，T2,3,t是优美图.

证明T2,3,t中有9+6t个顶点， 边数|E|=8+

6t.给出T2,2,t的顶点标号f如下:

f(x0)=0，f(x)=8+6t=|E|，f(y)=4+6t=

|E|-4；

f(x1)=3，f(x2)=2，f(x3)=1；

f(y1)=7+6t，f(y2)=6+6t，f(y3)=5+6t；

f(y11)=4，f(y12)=10,…,f(y1t)=3+6(t-1)；

f(y21)=f(y11)+1，f(y22)=f(y12)+1,…,f(y2t)=f(y1t)+1；

f(x11)=f(y21)+1，f(x12)=f(y22)+1， …,f(x1t)=f(y2t)+1；

f(x21)=f(x11)+1，f(x22)=f(x12)+1， …,f(x2t)=f(x1t)+1.

可以验证这是一个优美标号.

定理3T2,s,t是优美图.

证明T2,s,t中有3+2s+2st个顶点， 边数|E|=2+2s+2st.给出T2,s,t的顶点标号f如下:

f(x0)=0，f(x)=2+2s+2st=|E|，f(y)=

4+6t=|E|-(s+1)；

f(x1)=s，f(x2)=s-1， …,f(xs)=1；

f(y1)=|E|-1，f(y2)=|E|-2， …,f(ys)=

|E|-s；

f(y11)=s+1，f(y12)=s+1+2s， …,f(y1t)=

s+1++2s(t-1)；

f(y21)=f(y11)+1，f(y22)=f(y12)+1,…,f(y2t)=f(y1t)+1；

…,

f(ys1)=f(ys-1,1)+1，f(ys2)=f(ys-1,2)+1， …,f(yst)=f(ys-1,t)+1；

f(x11)=f(ys1)+1，f(x12)=f(ys2)+1， …,f(x1t)=f(yst)+1；

f(x21)=f(x11)+1，f(x22)=f(x12)+1， …,f(x2t)=f(x1t)+1；

…,

f(xs1)=f(xs-1,1)+1，f(xs2)=f(xs-1,2)+1， …,f(xst)=f(xs-1,t)+1.

可以验证这是一个优美标号.

定理4当s=2时，T2,2,t是奇优美图.

证明给出T2,2,t的顶点标号f如下:

f(x0)=0，f(x)=2|E|-1，f(y)=2|E|-7；

f(x1)=4，f(x2)=2，

f(y1)=2|E|-4，f(y2)=2|E|-6；

f(y11)=5，f(y12)=13,…,f(y1t)=5+8(t-1)；

f(y21)=f(y11)+2，f(y22)=f(y12)+2， …,f(y2t)=f(y1t)+2；

f(x11)=f(y21)+2，f(x12)=f(y22)+2， …,f(x1t)=f(y2t)+2；

f(x21)=f(x11)+2，f(x22)=f(x12)+2， …,f(x2t)=f(x1t)+2.

可以验证这是一个奇优美标号.

定理5当s=3时，T2,3,t是奇优美图.

证明给出T2,3,t的顶点标号f如下:

f(x0)=0，f(x)=2|E|-1，f(y)=2|E|-9；

f(x1)=6，f(x2)=4，f(x3)=2；

f(y1)=2|E|-4，f(y2)=2|E|-6，f(y3)=

2|E|-8；

f(y11)=7，f(y12)=19,…,

f(y1t)=5+12(t-1)；

f(y21)=f(y11)+2，f(y22)=f(y12)+2， …,f(y2t)=f(y1t)+2；

f(y31)=f(y21)+2，f(y32)=f(y22)+2， …,f(y3t)=f(y2t)+2；

f(x11)=f(y21)+2，f(x12)=f(y22)+2， …,f(x1t)=f(y2t)+2；

f(x21)=f(x11)+2，f(x22)=f(x12)+2， …,f(x2t)=f(x1t)+2；

f(x31)=f(x21)+2，f(x32)=f(x22)+2， …,f(x3t)=f(x2t)+2.

可以验证这是一个奇优美标号.

定理6T2,s,t是奇优美图.

证明给出T2,s,t的顶点标号f如下:

f(x0)=0，f(x)=2|E|-1，f(y)=2|E|-2s-3；

f(x1)=2s，f(x2)=2s-2， …,f(xs)=2s-2(s-1)；

f(y1)=2|E|-4，f(y2)=2|E|-6， …,f(ys)=2|E|-2(s+1)；

f(y11)=2s+1，f(y12)=2s+4s…,f(y1t)=2s+4s(t-1)；

f(y21)=f(y11)+2，f(y22)=f(y12)+2， …,f(y2t)=f(y1t)+2；

…,

f(ys1)=f(ys-1,1)+2，f(ys2)=f(ys-1,2)+2， …,f(yst)=f(ys-1,t)+2；

f(x11)=f(ys1)+2，f(x12)=f(ys2)+2， …,f(x1t)=f(yst)+2；

f(x21)=f(x11)+2，f(x22)=f(x12)+2， …,f(x2t)=f(x1t)+2；

…,

f(xs1)=f(xs-1,1)+2，f(xs2)=f(xs-1,2)+2， …,f(xst)=f(xs-1,t)+2.

可以验证这是一个奇优美标号.

定理7当s=2时，T2,2,t是k-优美图

(k>2).

证明给出T2,2,t的顶点标号f如下:

f(x0)=0，f(x)=|E|+k-1，f(y)=|E|+k-2；

f(x1)=5，f(x2)=4，f(y1)=2，f(y2)=1；

f(y11)=k+3，f(y12)=k+7， …,f(y1t)=k+3+4(t-1)；

f(y21)=f(y11)+1，f(y22)=f(y12)+1,…,f(y2t)=f(y1t)+1；

f(x11)=f(y21)+1，f(x12)=f(y22)+1， …,f(x1t)=f(y2t)+1；

f(x21)=f(x11)+1，f(x22)=f(x12)+1， …,f(x2t)=f(x1t)+1.

可以验证这是一个k-优美标号.

定理8当s=3时，T2,3,t是k-优美图(k>3).

证明给出T2,3,t的顶点标号f如下:

f(x0)=0，f(x)=|E|+k-1，f(y)=|E|+k-2；

f(x1)=7，f(x2)=6，f(x3)=5；

f(y1)=3，f(y2)=2，f(y3)=1；

f(y11)=k+4，f(y12)=k+10,…,f(y1t)=k+4+6(t-1)；

f(y21)=f(y11)+1，f(y22)=f(y12)+1,…,f(y2t)=f(y1t)+1；

f(y31)=f(y21)+1，f(y32)=f(y22)+1,…,f(y3t)=f(y21t)+1；

f(x11)=f(y21)+1，f(x12)=f(y22)+1， …,f(x1t)=f(y2t)+1；

f(x21)=f(x11)+1，f(x22)=f(x12)+1， …,f(x2t)=f(x1t)+1；

f(x31)=f(x21)+1，f(x32)=f(x22)+1， …,f(x3t)=f(x2t)+1.

可以验证这是一个k-优美标号.

定理9T2,s,t是k-优美图(k>s).

证明给出T2,s,t的顶点标号f如下:

f(x0)=0，f(x)=|E|+k-1，f(y)=|E|+k-2；

f(x1)=s+s+1，f(x2)=s+s， …,f(xs)=s+2；

f(y1)=s，f(y2)=s-1， …,f(ys)=1；

f(y11)=k+s+1，f(y12)=k+s+1+2s， …,f(y1t)=k+s+1++2s(t-1)；

f(y21)=f(y11)+1，f(y22)=f(y12)+1,…,f(y2t)=f(y1t)+1；

…,

f(ys1)=f(ys-1,1)+1，f(ys2)=f(ys-1,2)+1， …,f(yst)=f(ys-1,t)+1；

f(x11)=f(ys1)+1，f(x12)=f(ys2)+1， …,f(x1t)=f(yst)+1；

f(x21)=f(x11)+1，f(x22)=f(x12)+1， …,f(x2t)=f(x1t)+1；

…,

f(xs1)=f(xs-1,1)+1，f(xs2)=f(xs-1,2)+1， …,f(xst)=f(xs-1,t)+1.

可以验证, 这是一个k-优美标号.