吳躍生

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

1 引言與概念

本文所討論的圖均為無(wú)向簡(jiǎn)單圖，V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集，記號(hào)[m,n] 表示整數(shù)集合{m,m+1,…,n} ，其中m和n均為非負(fù)整數(shù)，且滿足0 ≤m＜n。未說(shuō)明的符號(hào)及術(shù)語(yǔ)均同文［1］。圖的優(yōu)美標(biāo)號(hào)問(wèn)題是組合數(shù)學(xué)中一個(gè)熱門(mén)課題［1-10］。

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

定義2［1］設(shè)f為G的一個(gè)優(yōu)美標(biāo)號(hào)，如果存在一個(gè)正整數(shù)k，使得對(duì)任意的uv∈E(G)有

f(u)＞k≥f(v)或f(u)≤k＜f(v)

成立，則稱(chēng)f為G的平衡標(biāo)號(hào)（或稱(chēng)G有平衡標(biāo)號(hào)f），且稱(chēng)k為f的特征。圖G稱(chēng)為平衡二分圖（balanced bipartite graph）。

顯然，若f為G的平衡標(biāo)號(hào)，則k是邊導(dǎo)出標(biāo)號(hào)為1的邊的兩個(gè)端點(diǎn)中標(biāo)號(hào)較小的頂點(diǎn)的標(biāo)號(hào)。

定義3［1］在平衡二分圖G中，設(shè)其優(yōu)美標(biāo)號(hào)θ的特征為k，并且θ（u0)=k，θ（v0)=k+1，則稱(chēng)u0為G的二分點(diǎn)，v0為G的對(duì)偶二分點(diǎn)。

定義4［2］G是一個(gè)優(yōu)美二部圖，其優(yōu)美標(biāo)號(hào)為θ，V(G)劃分成兩個(gè)集合X，Y，如果，則稱(chēng)θ是G的交錯(cuò)標(biāo)號(hào)。稱(chēng)G是在交錯(cuò)標(biāo)號(hào)θ下的交錯(cuò)圖。

定義5［3-4］V(G)={v1,v2,…,vn}的每個(gè)頂點(diǎn)vi都粘接了ri條懸掛邊（ri為自然數(shù)，i=1,2,…，k）所得到的圖，稱(chēng)為圖G的(r1,r2,…,rn) -冠，簡(jiǎn)記為G(r1,r2,…,rn)。特別地，當(dāng)r1=r2=…=rn=r時(shí)，稱(chēng)為圖G的r-冠。圖G的0-冠就是圖G。

本文討論了非連通圖C3(m,0,0)?G的優(yōu)美性。

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

定理1設(shè)G是一個(gè)p條邊的優(yōu)美圖，g是G的優(yōu)美標(biāo)號(hào)，p-1 不是g的標(biāo)號(hào)值，h是圖H特征為k的交錯(cuò)標(biāo)號(hào)，k+2 不是h的標(biāo)號(hào)值（k+2 ＜q，|E(H)| =q）則非連通圖G?H存在k+1 不是其標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。特別地，當(dāng)G是交錯(cuò)圖時(shí)，則非連通圖G?H存在k+1不是其標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

證設(shè)X，Y是交錯(cuò)圖H的一個(gè)二分化，且=k+1，|E(H) |=q。

定義非連通圖G?H的頂點(diǎn)標(biāo)號(hào)θ為

下面證明θ是非連通圖G?H的優(yōu)美標(biāo)號(hào)。

1）θ：X→［0，k］是單射（或雙射）；θ：Y→［k+1+p，p+q］-｛k+2+p｝是單射（或雙射）；θ：V(G)→［k+2，k+2+p］-｛k+1+p｝是單射（或雙射）；容易驗(yàn)證：θ：V(G?H)→［0，p+q］-｛k+1｝是單射（或雙射）。

2）θ′：E(G)→［1，p］是雙射。θ′：E(H)→［p+1，p+q］是雙射容易驗(yàn)證：θ′：E(G?H)→［1，p+q］是一一對(duì)應(yīng)。

由1）和2）可知θ就是非連通圖G?H的缺k+1標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

特別地，當(dāng)G是交錯(cuò)圖時(shí)，設(shè)X1，Y1是圖G的一個(gè)二分化，且=k1+1 ，令X2=X?X1，Y2=Y?Y1，有=k1+k+2 ＜=k1+k+3 則非連通圖G?H存在k+1不是其標(biāo)號(hào)值的特征為k1+k+2 的交錯(cuò)標(biāo)號(hào)。證畢。

引理1對(duì)任意自然數(shù)m，C3(m,0,0)存在缺標(biāo)號(hào)值m+2 的優(yōu)美標(biāo)號(hào)。

證設(shè)圈C3的頂點(diǎn)依次為v1,v2,v3，與頂點(diǎn)v1鄰接的端點(diǎn)（或葉）記為x1,j(j=1,2,…,m)，定義非連通圖C3(m,0,0) 的頂點(diǎn)標(biāo)號(hào)θ為：θ(v1)=3+m，θ(v2)=m，θ(v3)=m+1，θ(x1,j)=m-j,j=1,2,…,m，（當(dāng)m=0 時(shí)，θ(x1,j)=θ(v1)）。

容易驗(yàn)證：θ就是C3(m,0,0)缺標(biāo)號(hào)值m+2 的優(yōu)美標(biāo)號(hào)。

定理2對(duì)任意自然數(shù)m，圖G是特征為k且缺k+2 標(biāo)號(hào)值的交錯(cuò)圖（k+2 ＜q，|E(G)| =q），則非連通圖存在缺標(biāo)號(hào)值k+1的兩種不同的優(yōu)美標(biāo)號(hào)。

證由定理1 和引理1，可給出非連通圖C3(m,0,0)?G的第一種優(yōu)美標(biāo)號(hào)，下面給出非連通圖C3(m,0,0)?G的第二種優(yōu)美標(biāo)號(hào)。

設(shè)圈C3的頂點(diǎn)依次為v1,v2,v3，與頂點(diǎn)v1鄰接的端點(diǎn)（或葉）記為x1,j(j=1,2,…,m)，設(shè)X,Y是圖G的一個(gè)二分化，θ1是圖G的交錯(cuò)標(biāo)號(hào)，且=k+1。

定義非連通圖C3(m,0,0)?G的頂點(diǎn)標(biāo)號(hào)θ為

θ(v1)=k+2,θ(v2)=3+k,θ(v3)=5+k+m,θ(x1,j)=3+k+j，j=1,2,…,m，（當(dāng)m=0 時(shí)，θ(x1,j)=θ(v1)），

下面證明θ是非連通圖C3(m,0,0)?G的優(yōu)美標(biāo)號(hào)。

1）θ：X→［0，k］是單射（或雙射）；θ：Y→［k+m+4，q+m+3］-｛k+m+5｝是單射（或雙射）；θ：V(C3(m,0,0)) →［k+2 ，k+m+3］?k+m+5 是雙射；容易驗(yàn)證：θ：V（C3(m,0,0)?G）→［0，q+m+3］-｛k+1｝是單射（或雙射）。

2）=1+j,j=1,2,…,m;=1,=2+m,=3+m,：E(C3(m,0,0))→［1，m+3］是雙射；：E(G)→［m+4，q+m+3］是雙射。

由1）和2）可知θ就是非連通圖C3(m,0,0)?G的缺k+1標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。證畢。

例1由定理2可得非連通圖C3(4,0,0)?C4缺標(biāo)號(hào)值2的第一種優(yōu)美標(biāo)號(hào)為：C3（4，0，0）：10（3，4，5，6），7，8；C4：0，11，1，9；由定理2可得非連通圖C3(4,0,0)?C4缺標(biāo)號(hào)值2的第二種優(yōu)美標(biāo)號(hào)為：C3（4，0，0）：3（5，6，7，8），4，10；C4：0，11，1，9。

引理2［1］對(duì)任意自然數(shù)m，n，當(dāng)m≥2，n≥2 時(shí)，完備二分圖Km,n存在特征為m-1 且缺m+1 標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

證設(shè)完備二分圖Km,n的頂點(diǎn)二分劃為V1，V2，V1={v1,v2,…,vm}，V2={u1,u2,…,un}，令

θ(vi)=i-1,θ(vi)=i-1,i=1,2,…,m，θ(ui)=im,i=1,2,…,n

容易驗(yàn)證：對(duì)任意自然數(shù)m，n，當(dāng)m≥2，n≥2 時(shí)，完備二分圖Km,n存在特征為m-1 且缺m+1 標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

由引理2和定理2，有

推論3對(duì)任意自然數(shù)h，m，n，當(dāng)m≥2，n≥2 時(shí)，非連通圖C3(m,0,0)?Km,n存在且缺標(biāo)號(hào)值m的兩種不同的優(yōu)美標(biāo)號(hào)。

例2由推論3可得C3(4,0,0)?K3,2缺標(biāo)號(hào)值3的兩種不同的優(yōu)美標(biāo)號(hào)如圖1所示。

圖1 非連通圖C3(4,0,0)?K3,2 的兩種優(yōu)美標(biāo)號(hào)Fig.1 The graceful labeling of C3(4,0,0)?K3,2

我們把順序有一個(gè)公共點(diǎn)的m個(gè)C4的連通并圖記作Fm,4［1］。

引理3［1］對(duì)任意自然數(shù)m，圖Fm,4存在特征為m且缺m+2 標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

由引理3和定理2，有

推論4對(duì)任意自然數(shù)m，n，非連通圖C3(m,0,0)?Fn,4存在缺標(biāo)號(hào)值n+1的兩種不同的優(yōu)美標(biāo)號(hào)。

例3由推論4可得C3(4,0,0)?F3,4缺標(biāo)號(hào)值4的兩種不同的優(yōu)美標(biāo)號(hào)如圖2所示。

圖2 非連通圖C3(4,0,0)?F3,4 的兩種優(yōu)美標(biāo)號(hào)Fig.2 The graceful labeling of C3(4,0,0)?F3,4

我們把m個(gè)C4間順序加一條邊的圖記作∧C4,m［1］。

引理4［1］對(duì)任意自然數(shù)m，圖∧C4,m存在特征為2m-1且缺2m+1標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

由引理4和定理2，有

推論4對(duì)任意自然數(shù)m，n，非連通圖C3(m,0,0)?∧C4,n存在缺標(biāo)號(hào)值2n的兩種不同的優(yōu)美標(biāo)號(hào)。

例4由推論4可得C3(4,0,0)?∧C4,2缺標(biāo)號(hào)值4的兩種不同的優(yōu)美標(biāo)號(hào)如圖3所示。

圖3 非連通圖C3(4,0,0)ΛC4,2 的兩種優(yōu)美標(biāo)號(hào)Fig.3 The graceful labeling of C3(4,0,0)ΛC4,2

引理5［1］對(duì)任意自然數(shù)a,b，圖C4(a,0,b,0)存在特征為1且缺3 標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

證設(shè)C4上的頂點(diǎn)依次為u1,u2,u3,u4，與頂點(diǎn)u1鄰接的端點(diǎn)（或葉）記為y1,j，j=1,2,…,a，與頂點(diǎn)u3鄰接的端點(diǎn)（或葉）記為y3,j，j=1,2,…,b。

定義C4(a,0,b,0) 的頂點(diǎn)標(biāo)號(hào)θ為：θ(u1)=0,θ(u3)=1，θ(u4)=2 ，θ(y1,j)=5+a+b-j,j=1,2,…,a,（當(dāng)a=0 時(shí)，θ(y1,j)=θ(u1)），θ(u2)=4+b,θ(y3,j)=4+b-j，j=1,2,…,b,（當(dāng)b=0 時(shí)，θ(y3,j)=θ(u3)）。

下面證明θ是C4(a,0,b,0)的優(yōu)美標(biāo)號(hào)。

1）容易驗(yàn)證：θ：V(C4(a,0,b,0))→[0,4+a+b]-{3}是一一映射。

2）(u1u2)=|θ(u1)-θ(u2)|=4+b,(u3u2)=|θ(u3)-θ(u2)|=3+b,(u3u4)=|θ(u3)-θ(u4)|=1,=|θ(u1) -θ(u4)|=2,(u1y1,j)=|θ(u1) -θ(y1,j)|=4+a+b-j,j=1,2,…,a，(u3y3,1)=|θ(u3)-θ(y3,1) |=3+b-j,

由1）和2）可知θ是C4(a,0,b,0)的優(yōu)美標(biāo)號(hào)。

令X={u1,u3}，Y={u2,u4}?{y1,j|j=1,2,…,a}?{y3,j|j=1,2,…,b}則有

所以，θ就是圖C4(a,0,b,0)特征為1，且缺3的交錯(cuò)標(biāo)號(hào)。

由引理5和定理2，有

推論5對(duì)任意自然數(shù)a,b,m，非連通圖C3(m,0,0)?C4(a,0,b,0)存在缺標(biāo)號(hào)值2 的兩種不同的優(yōu)美標(biāo)號(hào)。

例5由推論5可得C3(4,0,0)?C4(3,0,5,0)缺標(biāo)號(hào)值2的兩種不同的優(yōu)美標(biāo)號(hào)如圖4所示。

圖4 非連通圖C3(4,0,0)?C4(3,0,5,0)的兩種優(yōu)美標(biāo)號(hào)Fig.4 The graceful labeling of C3(4,0,0)?C4(3,0,5,0)

［1］馬杰克.優(yōu)美圖［M］.北京：北京大學(xué)出版社，1991：1-247.

［2］楊顯文.關(guān)于C4m蛇的優(yōu)美性［J］.工程數(shù)學(xué)學(xué)報(bào)，1995，12（4）：108-112.

［3］吳躍生.關(guān)于圈C4h的（r1，r2，…，r4h）-冠的優(yōu)美性［J］.華東交通大學(xué)學(xué)報(bào)，2011，28（1）：77-80.

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

［5］吳躍生.關(guān)于圖P6k+53∪Pn3的優(yōu)美性［J］吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，33（3）：4-7.

［6］吳躍生，徐保根.兩類(lèi)非連通圖(P2∨)(0，0,r1,0,…,0,rn)?St(m)及(P2∨)(r1+a,r2,0,…,0)?Gr的優(yōu)美性［J］.中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，51（5）：63-66.

［7］吳躍生.圖C7（r1，r2，r3，，r4，r5，0，0）∪St（m）的優(yōu)美性［J］.吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，33（5）：9-1.

［8］吳躍生，王廣富.關(guān)于C4h+1⊙K1的（Gr1，Gr2，…，Gr4h+1，Gr4h+2）-冠的優(yōu)美性［J］.山東大學(xué)學(xué)報(bào)，2013，48（4）：25-27.

［9］吳躍生.關(guān)于圈C4h+3的（Gr1，Gr2，…，Gr4h+3）-冠的優(yōu)美性［J］.吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，34（4）：1-6.

［10］吳躍生，王廣富，徐保根.非連通圖C2n+1∪Gn-1的優(yōu)美性［J］.華東交通大學(xué)學(xué)報(bào)，2012，29（6）：26-29.