兩類非連通圖(P2∨，0,r1,0,…,0,rn)∪St(m)及(P2∨,r2,0,…,0)∪Gr的優(yōu)美性*

吳躍生,徐保根

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西 南昌330013)

圖的標(biāo)號(hào)問題是組合數(shù)學(xué)中一個(gè)熱門課題。它不僅屬于圖論領(lǐng)域，也屬于設(shè)計(jì)理論的范疇，主要應(yīng)用于編碼設(shè)計(jì)、變壓器箱設(shè)計(jì)、雷達(dá)脈沖、射電天文學(xué)、通訊網(wǎng)絡(luò)、晶體結(jié)構(gòu)中原子位置的測(cè)定和導(dǎo)彈控制碼等方面。

1 概念

本文所討論的圖均為無向簡(jiǎn)單圖，V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集。

定義1[1]對(duì)于一個(gè)圖G=(V,E)， 如果存在一個(gè)單射θ:V(G) →{ 0,1,2,…，|E(G)|}使得對(duì)所有邊e=(u,v)∈E(G)， 由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的E(G) →{1,2,…,|E(G)|}是一個(gè)雙射，則稱G是優(yōu)美圖,θ是G的一組優(yōu)美標(biāo)號(hào)，稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎo)值。

定義2[2-12]V(G)= (v1,v2,…,vn)的每個(gè)頂點(diǎn)vi都粘接了ri條懸掛邊(ri≥0是整數(shù)，i=1,2,…,n)所得到的圖，稱為圖G的(r1,r2,…,rn)-冠，簡(jiǎn)記為G(r1,r2,…,rn)。 特別地，當(dāng)r1=r2=…=rn=r時(shí)，稱為圖G的r-冠。圖G的0-冠就是圖G。

{y1,y2,xi,zj,1≤i≤n,0≤j≤m},

{y1y2,y1xi,y2xi,z0zk,1≤i≤n,0≤k≤m}

{y1,y2,xi,1≤i≤n}∪V(Gn-1),

{y1y2,y1xi,y2xi,1≤i≤n}∪E(Gn-1)

{y1,y2,xi,x1,s,xn,t,zj,

1≤i≤n,0≤s≤r1,0≤t≤r2,0≤j≤m};

{y1y2,y1xi,y2xi,x1x1,s,xnxn,t,z0zk,

1≤i≤n,0≤s≤r1,0≤t≤r2,1≤k≤m}

{y1,y2,xi,y1,s,y1,t,

1≤i≤n,0≤s≤r1+a,0≤t≤r2}∪V(Gr) ;

{y1y2,y1xi,y2xi,y1y1,s,y2y2,t,

1≤i≤n,0≤s≤r1+a,0≤t≤r2}∪E(Gr),

2 主要結(jié)果及其證明

當(dāng)rj=0時(shí),xj,i=xj,j=1,n;i=1,2,…,rj;

當(dāng)rj≠0 (j=1,n)時(shí),

θ(x1,i)=2n+m+r1+rn+2-i,i=1,2,…,r1,

θ(y1)=2n+m+rn+1,θ(y2)=2n+m+rn,

θ(xn,i)=2n+m+rn-i,i=1,2,…,rn,

θ(xi)=2(i-1),i=1,2,…,n，

θ(z0)=2n-3;θ(zj)=2n+j-2,j=1,2,…,m

(i)由于

0=θ(x1)<θ(x2)<…<θ(xn-1)<θ(z0)<

θ(xn)<θ(z1)<θ(z2)<…<θ(zm)<

θ(xn,rn)<θ(xn,rn-1)<…<θ(xn,1)<θ(y2)<

θ(y1)<θ(x1,r1)<θ(x1,r1-1)<…<θ(x1,1)=

2n+m+r1+rn+1

(ii)由點(diǎn)標(biāo)號(hào)θ導(dǎo)出的邊標(biāo)號(hào)θ′為：

θ′(y1y2)=1,θ′(x1x1,i)=2n+m+r1+rn+2-i,

i=1,2,…,r1，

θ′(y1xi)=2n+m+rn-1-2i,i=1,2,…,n，

θ′(y2xi)=2n+m+rn-2-2i,i=1,2,…,n，

θ′(xnxn,i)=m+rn+2-i,i=1,2,…,rn，

θ′(z0zi)=i+1,i=1,2,…,m

在定理1中，令r1=rn=0,有以下推論。

圖1 圖(P2∨(0,0,2,0,3)∪St(4)的優(yōu)美標(biāo)號(hào)

當(dāng)r1+a=0時(shí),x1,i=x1,i=1,2,…,r1+a;

當(dāng)r2=0時(shí),x2,i=x2,i=1,2,…,r2;

當(dāng)r1+a≠0,r2≠0時(shí),

g(y1)=0,g(y2)=n,

g(xi)=3n+r2+1-i,i=1,2,…,n，

g(y2,i)=2n+r2+1-i,i=1,2,…,r2,

g(v)=h(v)+n+1,v∈V(Gr)

(i) 由于

0=g(y1)

g(y2，r2)

g(xn)

g(y1，r1-1)<…

(ii) 由點(diǎn)標(biāo)號(hào)g導(dǎo)出的邊標(biāo)號(hào)g′為：

g′(y1y2)=n,g′(xi)=3n+r2+1-i,i=1,2,…,n，

g′(y2y2，i)=2n+r2+1-i,i=1,2,…,r2，

g′(y1xi)=3n+r2+1-i,i=1,2,…,n，

g′(y2xi)=2n+r2+1-i,i=1,2,…,n，

g′(e)=h′(e)，e∈E(Gr)

易見,對(duì)于自然數(shù)n,r1,r2,a,r,則當(dāng)n≥2時(shí)，

在定理2中，令r1+a=r2=0,有以下推論。

圖2 圖(P2∨(2,3,0,0,0,0,0,0)∪T6的優(yōu)美標(biāo)號(hào)

圖3 圖(P2∨(2,3,0,0,0,0,0,0)∪G5的優(yōu)美標(biāo)號(hào)

定義7[1]設(shè)Cn是長(zhǎng)為n的圈，當(dāng)n>3時(shí)，聯(lián)圖(P1∨Cn)稱為輪，記Wn。

引理1 所有的輪Wn都是優(yōu)美圖。

圖4 圖(P2∨(3+4,2,0,…,0)∪W4的優(yōu)美標(biāo)號(hào)

參考文獻(xiàn)：

[1]馬杰克.優(yōu)美圖[M].北京:北京大學(xué)出版社，1991.

[2]吳躍生，李詠秋.關(guān)于圈Cn的(r1,r2,…,rn)-冠(n=7,8)的優(yōu)美性[J].阜陽(yáng)師范學(xué)院學(xué)報(bào)：自然科學(xué)版， 2010,27(3)：20-23.

[3]吳躍生，李詠秋.關(guān)于圈C11的(r1,r2,…,r11)冠的優(yōu)美性[J].長(zhǎng)春師范學(xué)院學(xué)報(bào)，2010,29(6)：4-8.

[4]吳躍生，李詠秋.再探圈Cn的(r1,r2,…,rn)-冠(n=7,8)的優(yōu)美性[J].阜陽(yáng)師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2010,27(4)：1-4.

[5]吳躍生，李詠秋.關(guān)于圈C3的(1,2a,2a+1)-冠的優(yōu)美性[J].河南教育學(xué)院學(xué)報(bào)，2010,4: 1-2.

[6]吳躍生.關(guān)于圈C4h的(r1,r2,…,r4h)-冠的優(yōu)美性[J].華東交通大學(xué)學(xué)報(bào),2011,28(1): 77-80.

[7]吳躍生,李詠秋.關(guān)于圈C4h+3的(r1,r2,…,r4h)-冠的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2011,32(6): 1-4.

[8]吳躍生，李詠秋.關(guān)于圖ω4,4的(r1,r2,…,r7)-冠的優(yōu)美性[J].宜春學(xué)院學(xué)報(bào)，2010,32(12)：1-3.

[9]吳躍生，李詠秋.關(guān)于圖ω5，7的(r1,r2,…,r11)-冠的優(yōu)美性[J].嘉應(yīng)學(xué)院學(xué)報(bào)，2011,29(5): 5-8.

[10]吳躍生，李詠秋.關(guān)于圖ω5，6的(r1,r2,…,r10)-冠的優(yōu)美性[J].北京聯(lián)合大學(xué)學(xué)報(bào)，2011,25(2): 60-61.

[11]吳躍生.關(guān)于圖ω4，6的(r1,r2,…,r9)-冠的優(yōu)美性[J].宜春學(xué)院學(xué)報(bào)，2011,33(8)：1-3.

[12]康芳茂，吳躍生.關(guān)于Cn⊙k1的(r0,r1,r2,…,rn)-冠(n=6)的優(yōu)美性[J].懷化學(xué)院學(xué)報(bào),2011,30(5): 8-10.

[15]魏麗俠，張昆龍.幾類并圖的優(yōu)美標(biāo)號(hào)[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2008,47( 3): 10-13.

[16]蔡華，魏麗俠，呂顯瑞.非連通圖(P1∨Pn)∪Gr和(P1∨Pn)∪ (P3∨Kr)及Wn∪St(m)的優(yōu)美性[J].吉林大學(xué)學(xué)報(bào)：理學(xué)版，2007,45(4): 539-543.

[17]蔡華.幾類非連通圖的優(yōu)美性[D].吉林大學(xué)碩士學(xué)位論文,2007.