非連通圖C3（m，0，0）∪G的優美性

吳躍生

（華東交通大學基礎科學學院，江西南昌330013）

1 引言與概念

本文所討論的圖均為無向簡單圖，V(G)和E(G)分別表示圖G的頂點集和邊集，記號[m,n] 表示整數集合{m,m+1,…,n} ，其中m和n均為非負整數，且滿足0 ≤m＜n。未說明的符號及術語均同文［1］。圖的優美標號問題是組合數學中一個熱門課題［1-10］。

定義1［1］對于一個圖G=(V,E)如果存在一個單射θ：V(G)→［0，|E(G)|］使得對所有邊e=(u,v)∈E(G)，由θ′(e)=|θ(u)-θ(v) |導出的E(G)→［1，|E(G) |］是一個雙射，則稱G是優美圖，θ是G的一組優美標號，稱θ′為G的邊上的由θ導出的誘導值。

定義2［1］設f為G的一個優美標號，如果存在一個正整數k，使得對任意的uv∈E(G)有

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

成立，則稱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的對偶二分點。

定義4［2］G是一個優美二部圖，其優美標號為θ，V(G)劃分成兩個集合X，Y，如果，則稱θ是G的交錯標號。稱G是在交錯標號θ下的交錯圖。

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

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

2 主要結果及其證明

定理1設G是一個p條邊的優美圖，g是G的優美標號，p-1 不是g的標號值，h是圖H特征為k的交錯標號，k+2 不是h的標號值（k+2 ＜q，|E(H)| =q）則非連通圖G?H存在k+1 不是其標號值的優美標號。特別地，當G是交錯圖時，則非連通圖G?H存在k+1不是其標號值的交錯標號。

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

定義非連通圖G?H的頂點標號θ為

下面證明θ是非連通圖G?H的優美標號。

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

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

由1）和2）可知θ就是非連通圖G?H的缺k+1標號值的優美標號。

特別地，當G是交錯圖時，設X1，Y1是圖G的一個二分化，且=k1+1 ，令X2=X?X1，Y2=Y?Y1，有=k1+k+2 ＜=k1+k+3 則非連通圖G?H存在k+1不是其標號值的特征為k1+k+2 的交錯標號。證畢。

引理1對任意自然數m，C3(m,0,0)存在缺標號值m+2 的優美標號。

證設圈C3的頂點依次為v1,v2,v3，與頂點v1鄰接的端點（或葉）記為x1,j(j=1,2,…,m)，定義非連通圖C3(m,0,0) 的頂點標號θ為：θ(v1)=3+m，θ(v2)=m，θ(v3)=m+1，θ(x1,j)=m-j,j=1,2,…,m，（當m=0 時，θ(x1,j)=θ(v1)）。

容易驗證：θ就是C3(m,0,0)缺標號值m+2 的優美標號。

定理2對任意自然數m，圖G是特征為k且缺k+2 標號值的交錯圖（k+2 ＜q，|E(G)| =q），則非連通圖存在缺標號值k+1的兩種不同的優美標號。

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

設圈C3的頂點依次為v1,v2,v3，與頂點v1鄰接的端點（或葉）記為x1,j(j=1,2,…,m)，設X,Y是圖G的一個二分化，θ1是圖G的交錯標號，且=k+1。

定義非連通圖C3(m,0,0)?G的頂點標號θ為

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

下面證明θ是非連通圖C3(m,0,0)?G的優美標號。

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 是雙射；容易驗證：θ：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標號值的優美標號。證畢。

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

引理2［1］對任意自然數m，n，當m≥2，n≥2 時，完備二分圖Km,n存在特征為m-1 且缺m+1 標號值的交錯標號。

證設完備二分圖Km,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

容易驗證：對任意自然數m，n，當m≥2，n≥2 時，完備二分圖Km,n存在特征為m-1 且缺m+1 標號值的交錯標號。

由引理2和定理2，有

推論3對任意自然數h，m，n，當m≥2，n≥2 時，非連通圖C3(m,0,0)?Km,n存在且缺標號值m的兩種不同的優美標號。

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

圖1 非連通圖C3(4,0,0)?K3,2 的兩種優美標號Fig.1 The graceful labeling of C3(4,0,0)?K3,2

我們把順序有一個公共點的m個C4的連通并圖記作Fm,4［1］。

引理3［1］對任意自然數m，圖Fm,4存在特征為m且缺m+2 標號值的交錯標號。

由引理3和定理2，有

推論4對任意自然數m，n，非連通圖C3(m,0,0)?Fn,4存在缺標號值n+1的兩種不同的優美標號。

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

圖2 非連通圖C3(4,0,0)?F3,4 的兩種優美標號Fig.2 The graceful labeling of C3(4,0,0)?F3,4

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

引理4［1］對任意自然數m，圖∧C4,m存在特征為2m-1且缺2m+1標號值的交錯標號。

由引理4和定理2，有

推論4對任意自然數m，n，非連通圖C3(m,0,0)?∧C4,n存在缺標號值2n的兩種不同的優美標號。

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

圖3 非連通圖C3(4,0,0)ΛC4,2 的兩種優美標號Fig.3 The graceful labeling of C3(4,0,0)ΛC4,2

引理5［1］對任意自然數a,b，圖C4(a,0,b,0)存在特征為1且缺3 標號值的交錯標號。

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

定義C4(a,0,b,0) 的頂點標號θ為：θ(u1)=0,θ(u3)=1，θ(u4)=2 ，θ(y1,j)=5+a+b-j,j=1,2,…,a,（當a=0 時，θ(y1,j)=θ(u1)），θ(u2)=4+b,θ(y3,j)=4+b-j，j=1,2,…,b,（當b=0 時，θ(y3,j)=θ(u3)）。

下面證明θ是C4(a,0,b,0)的優美標號。

1）容易驗證：θ：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)的優美標號。

令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的交錯標號。

由引理5和定理2，有

推論5對任意自然數a,b,m，非連通圖C3(m,0,0)?C4(a,0,b,0)存在缺標號值2 的兩種不同的優美標號。

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

圖4 非連通圖C3(4,0,0)?C4(3,0,5,0)的兩種優美標號Fig.4 The graceful labeling of C3(4,0,0)?C4(3,0,5,0)

［1］馬杰克.優美圖［M］.北京：北京大學出版社，1991：1-247.

［2］楊顯文.關于C4m蛇的優美性［J］.工程數學學報，1995，12（4）：108-112.

［3］吳躍生.關于圈C4h的（r1，r2，…，r4h）-冠的優美性［J］.華東交通大學學報，2011，28（1）：77-80.

［4］吳躍生，李詠秋.關于圈C4h+3的（r1，r2，…，r4h）-冠的優美性［J］.吉首大學學報：自然科學版，2011，32（6）：1-4.

［5］吳躍生.關于圖P6k+53∪Pn3的優美性［J］吉首大學學報：自然科學版，2012，33（3）：4-7.

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

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

［8］吳躍生，王廣富.關于C4h+1⊙K1的（Gr1，Gr2，…，Gr4h+1，Gr4h+2）-冠的優美性［J］.山東大學學報，2013，48（4）：25-27.

［9］吳躍生.關于圈C4h+3的（Gr1，Gr2，…，Gr4h+3）-冠的優美性［J］.吉首大學學報：自然科學版，2013，34（4）：1-6.

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