一類直徑為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-優美標號.