吳躍生，王廣富，徐保根

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

1 引言與預(yù)備知識

優(yōu)美圖集廣泛的應(yīng)用性和趣味性于一身，因而優(yōu)美圖的研究是圖論中較為活躍的課題之一[1-20].許多學(xué)者對非連通圖的優(yōu)美性進行了研究[4-18].本文考慮非連通圖（P1∨Pm）∪C4n∪P2的優(yōu)美性.

本文所討論的圖均為無向簡單圖，V（G）和E（G）分別表示圖G的頂點集和邊集，未說明的符號及術(shù)語均同文獻[1].

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

定義2[1]若一個圖G的頂點集V（G）能分成2個非空子集X和Y，使得X∪Y=V（G），X∩Y且G的每條邊的端點分別在X和Y中，則稱G為二分圖，記作 G=（X，Y；E），二分劃記為（X，Y）；如果G是優(yōu)美的，則稱為優(yōu)美二分圖.

定義3[3]設(shè)G是一個優(yōu)美二分圖，其優(yōu)美標號為θ，將V（G）劃分成2個集合X、Y，如果則稱θ是G的交錯標號.稱G是在交錯標號θ下的交錯圖.

定義4[1]設(shè)θ為G的一個優(yōu)美標號，如果存在正整數(shù) k，使得對任意的（u，v）∈E（G），有

成立，則稱θ為G的平衡標號（或稱G有平衡標號θ），且稱k為θ的特征.圖G稱為平衡二分圖.

顯然，若θ為G的平衡標號，則k是邊導(dǎo)出標號為1的邊的2個端點中標號較小的頂點的標號.

由定義3和定義4知：平衡圖與交錯圖等價，平衡圖的平衡標號θ的特征

定義5[1]設(shè)圖G1和G2不相交，在G1∪G2中，把G1的每個頂點和G2的每個頂點連接起來所得到的圖叫做G1和G2的聯(lián)圖，記作G1∨G2.

2 主要結(jié)果

引理1 如果優(yōu)美圖G不存在a的優(yōu)美值，a為自然數(shù)（1≤a≤|E（G）|-1），交錯圖H關(guān)于交錯標號的特征為k，交錯圖H不存在k+1+a的優(yōu)美值，則非連通圖G∪H∪P2是優(yōu)美圖.

證明 設(shè)G的優(yōu)美標號為 θ，|E（G）|=n，|E（H）|=m-1，θ1是圖H的交錯標號，其特征為k，（X，Y）是H的二分劃v1v2，定義非連通圖G∪H∪P2的標號θ2如下：

下面證明θ2是非連通圖G∪H∪P2的優(yōu)美標號.

（1）非連通圖G∪H∪P2中G的頂點標號集合是{k+1，k+2，…，k+a}∪{k+a+2，k+a+3，…，n+k+1}的子集，G的頂點標號互不相同.

在優(yōu)美標號θ下，圖G邊導(dǎo)出標號集合是{1，2，…，n}，可知在標號θ2下，圖G邊導(dǎo)出標號集合還是{1，2，…，n}.

（2）非連通圖G∪H∪P2中H的頂點標號集合是{0，1，…，k}∪{k+2+n，k+3+n，…，k+1+a+n}∪{k+3+a+n，k+4+a+n，…，n+m} 的子集，邊導(dǎo)出標號集合是{n+2，n+3，…，m+n}.

（3）非連通圖G∪H∪P2中P2的頂點標號集合是{k+1+a，k+1+a+n+1}，邊導(dǎo)出標號集合是{n+1}.

由（1）、（2）和（3）可知 θ2是非連通圖 G∪H∪P2的優(yōu)美標號.證畢.

引理2[1]設(shè)θ是圖G的一個優(yōu)美標號，對任意的頂點 v∈V（G），定義 θ：θ（v）=|E（G）|- θ（v），v∈V（G），則θ是一個異于θ的優(yōu)美標號.

引理3 設(shè)Pn是n個頂點的路，則P1∨Pn是優(yōu)美圖.

證明 記 P1和 Pn上的頂點依次為 v0和 v1，v2，…，vn，定義P1∨Pn的第1種頂點標號θ為：

θ（v0）=0，θ（v2i）=2i-1，i=1，2，…，n/2，n為偶數(shù)；i=1，2，…，（n-1）/2，n為奇數(shù)

θ（v2i-1）=2n-（2i-1），i=1，2，…，n/2，n 為偶數(shù)；i=1，2，…，（n+1）/2，n為奇數(shù)容易驗證，θ是P1∨Pn的優(yōu)美標號，且缺標號值2，4，…，2n-2.定義 θ：

由引理2知θ是一個異于θ的優(yōu)美標號，且缺標號值1，3，…，2n-3.

定義P1∨Pn的第2種頂點標號θ為：

θ（v0）=2n-1，θ（v2i）=n-i，i=1，2，…，n/2，n為偶數(shù)；i=1，2，…，（n-1）/2，n為奇數(shù)

θ（v2i-1）=i-1，i=1，2，…，n/2，n 為偶數(shù)；i=1，2，…，（n+1）/2，n為奇數(shù)

容易驗證，θ是P1∨Pn的優(yōu)美標號，且缺標號值n，n+1，…，2n-2.定義 θ：

θ（v）=|E（P1∨Pn）|- θ（v） v∈V（P1∨Pn）

由引理2知θ是一個異于θ的優(yōu)美標號，且缺標號值1，2，…，n-1.

引理4 設(shè)C4n是4n個頂點的圈，則C4n存在特征為2n-1，且缺3n的交錯標號.

證明 記圈C4n上的頂點依次為v1，v2，…，v4n，定義圈C4n的頂點標號θ為

容易驗證，θ就是圈C4n的特征為2n-1，且缺3n的交錯標號.

定理 設(shè)m，n為任意正整數(shù)，當m≥2，1≤n≤2m-2 時，非連通圖（P1∨Pm）∪C4n∪P2是優(yōu)美圖.

證明 由引理3知，圖P1∨Pm存在缺標號值為1，2，…，m-2的優(yōu)美標號.由引理4知，圈C4n存在特征為2n-1，且缺3n的交錯標號.注意到3n=（2n-1）+1+n，由引理 1可知，當 m≥2，1≤n≤2m-2時，非連通圖（P1∨Pm）∪C4n∪P2是優(yōu)美圖.

例（P1∨P5）∪C4n∪P2（1≤n≤8）的第1種優(yōu)美標號如下：

（P1∨P5）∪C4∪P2的優(yōu)美標號：P1的標號為 11；P5上各點的標號依次為 2，10，4，8，6；C4上各點的標號依次為0，14，1，12；P2上各點的標號依次為3，13.注：（P1∨P5）的優(yōu)美標號：P1的標號為 9；P5上各點的標號依次為0，8，2，6，4；C4上缺標號值3的各點的優(yōu)美標號依次為0，4，1，2.

（P1∨P5）∪C12∪P2的優(yōu)美標號：P1的標號為 15；P5上各點的標號依次為 6，14，8，12，10；C12上各點的標號依次為 0，22，1，21，2，20，3，18，4，17，5，16；P2上各點的標號依次為 9，19.注：（P1∨P5）的優(yōu)美標號：P1的標號為9；P5上各點的標號依次為0，8，2，6，4；C12上缺標號值9的各點的優(yōu)美標號依次為0，12，1，11，2，10，3，8，4，7，5，6.

（P1∨P5）∪C20∪P2的優(yōu)美標號：P1的標號為 19；P5上各點的標號依次為 10，18，12，16，14；C20上各點的標號依次為 0，30，1，29，2，28，3，27，4，26，5，24，6，23，7，22，8，21，9，20；P2上各點的標號依次為 15，25.注：（P1∨P5）的優(yōu)美標號：P1的標號為9；P5上各點的標號依次為 0，8，2，6，4；C20上缺標號值15的各點的優(yōu)美標號依次為0，20，1，19，2，18，3，17，4，16，5，14，6，13，7，12，8，11，9，10.

（P1∨P5）∪C28∪P2的優(yōu)美標號：P1的標號為 23；P5上各點的標號依次為 14，22，16，20，18；C28上各點的標號依次為 0，38，1，37，2，36，3，35，4，34，5，33，6，32，7，30，8，29，9，28，10，27，11，26，12，25，13，24；P2上各點的標號依次為 21，31.注：（P1∨P5）的優(yōu)美標號：P1的標號為9；P5上各點的標號依次為 0，8，2，6，4；C28上缺標號值 21的各點的優(yōu)美標號依次為 0，28，1，27，2，26，3，25，4，24，5，23，6，22，7，20，8，19，9，18，10，17，11，16，12，15，13，14.

（P1∨P5）∪C8∪P2的優(yōu)美標號：P1的標號為 4；P5上各點的標號依次為13，5，11，7，9；C8上各點的標號依次為 0，18，1，17，2，15，3，14；P2上各點的標號依次為 6，16.注：（P1∨P5）的優(yōu)美標號：P1的標號為 0；P5上各點的標號依次為 9，1，7，3，5；C8上缺標號值6的各點的優(yōu)美標號依次為0，8，1，7，2，5，3，4.

（P1∨P5）∪C16∪P2的優(yōu)美標號：P1的標號為 8；P5上各點的標號依次為17，9，15，11，13；C16上各點的標號依次為 0，26，1，25，2，24，3，23，4，21，5，20，6，19，7，18；P2上各點的標號依次為 12，22.注：（P1∨P5）的優(yōu)美標號：P1的標號為0；P5上各點的標號依次為 9，1，7，3，5；C16上缺標號值 12的各點的優(yōu)美標號依次為 0，16，1，15，2，14，3，13，4，11，5，10，6，9，7，8.

（P1∨P5）∪C24∪P2的優(yōu)美標號：P1的標號為 12；P5上各點的標號依次為 21，13，19，15，17；C24上各點的標號依次為 0，34，1，33，2，32，3，31，4，30，5，29，6，27，7，26，8，25，9，4，10，23，11，22；P2上各點的標號依次為 18，28.注：（P1∨P5）的優(yōu)美標號：P1的標號為0；P5上各點的標號依次為9，1，7，3，5；C24上缺標號值18的各點的優(yōu)美標號依次為0，24，1，23，2，22，3，21，4，20，5，19，6，17，7，16，8，15，9，14，10，13，11，12.

（P1∨P5）∪C32∪P2的優(yōu)美標號：P1的標號為 16；P5上各點的標號依次為 25，17，23，19，21；C32上各點的標號依次為 0，42，1，41，2，40，3，39，4，38，5，37，6，36，7，35，8，33，9，32，10，31，11，30，12，29，13，28，14，27，15，26；P2上各點的標號依次為 24，34.注：（P1∨P5）的優(yōu)美標號：P1的標號為 0；P5上各點的標號依次為9，1，7，3，5；C32上缺標號值24的各點的優(yōu)美標號依次為 0，32，1，31，2，30，3，29，4，28，5，27，6，26，7，25，8，23，9，22，10，21，11，20，12，19，13，18，14，17，15，16.

（P1∨P5）∪C4n∪P2（1≤n≤8）的第2種優(yōu)美標號如下：

（P1∨P5）∪C4∪P2的優(yōu)美標號：P1的標號為 2；P5上各點的標號依次為11，7，10，8，9；C4上各點的標號與第一種標號相同；P2上各點的標號依次為3，13.注：（P1∨P5）的優(yōu)美標號：P1的標號為 0；P5上各點的標號依次為9，5，8，6，7.

（P1∨P5）∪C8∪P2的優(yōu)美標號：P1的標號為 4；P5上各點的標號依次為13，9，12，10，11；C8上各點的標號與第一種標號相同；P2上各點的標號依次為6，16.注：（P1∨P5）的優(yōu)美標號：P1的標號為 0；P5上各點的標號依次為 9，5，8，6，7.

（P1∨P5）∪C12∪P2的優(yōu)美標號：P1的標號為 6；P5上各點的標號依次為 15，11，14，12，13；C12上各點的標號與第一種標號相同；P2上各點的標號依次為9，19.注：（P1∨P5）的優(yōu)美標號：P1的標號為 0；P5上各點的標號依次為9，5，8，6，7.

（P1∨P5）∪C16∪P2的優(yōu)美標號：P1的標號為 8；P5上各點的標號依次為 17，13，16，14，15；C16上各點的標號與第一種標號相同；P2上各點的標號依次為12，22.注：（P1∨P5）的優(yōu)美標號：P1的標號為 0；P5上各點的標號依次為9，5，8，6，7.

（P1∨P5）∪C20∪P2的優(yōu)美標號：P1的標號為 19；P5上各點的標號依次為 10，14，11，13，12；C20上各點的標號與第一種標號相同；P2上各點的標號依次為15，25.注：（P1∨P5）的優(yōu)美標號：P1的標號為 9；P5上各點的標號依次為0，4，1，3，2.

（P1∨P5）∪C24∪P2的優(yōu)美標號：P1的標號為 21；P5上各點的標號依次為 12，16，13，15，14；C24上各點的標號與第一種標號相同；P2上各點的標號依次為18，28.注：（P1∨P5）的優(yōu)美標號：P1的標號為 9；P5上各點的標號依次為0，4，1，3，2.

（P1∨P5）∪C28∪P2的優(yōu)美標號：P1的標號為 23；P5上各點的標號依次為 14，18，15，17，16；C28上各點的標號與第一種標號相同；P2上各點的標號依次為21，31.注：（P1∨P5）的優(yōu)美標號：P1的標號為 9；P5上各點的標號依次為0，4，1，3，2.

（P1∨P5）∪C32∪P2的優(yōu)美標號：P1的標號為 25；P5上各點的標號依次為 16，20，17，19，18；C32上各點的標號與第一種標號相同；P2上各點的標號依次為24，34.注：（P1∨P5）的優(yōu)美標號：P1的標號為 9；P5上各點的標號依次為0，4，1，3，2.

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

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

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

[6]張志尚，張慶成，王春月.關(guān)于（s＜C4：n＞）∪Pm的優(yōu)美性[J].東北師范大學(xué)學(xué)報：自然科學(xué)版，2011，43（3）：14-18.

[10]張志尚，王春月，張慶成.關(guān)于wn∪wn∪Pm的優(yōu)美性[J].東北師范大學(xué)學(xué)報：自然科學(xué)版，2010，42（4）：30-34.

[11]吳躍生，徐保根.兩類非連通圖（P2∨Kn）（0，0，r1，0，…，0，rn）∪St（m）及（P2∨Kn）（r1+a，r2，0，…，0，）∪Gr的優(yōu)美性[J].中山大學(xué)學(xué)報：自然科學(xué)版，2012，51（5）：63-66.

[12]王濤，劉海生，李德明.和輪相關(guān)圖的優(yōu)美性[J].中山大學(xué)學(xué)報：自然科學(xué)版，2011，50（6）：16-19.

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

[15]蔡華.幾類非連通圖的優(yōu)美性[D].長春：吉林大學(xué)，2007.

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

[17]GALLIAN JA.A dynamic survey of graph labeling[J].The Electronic Journal of Combinatorics，2013，16（6）：1-308.

[18]魏麗俠，張昆龍.圖K1∨Cn的非連通并圖的優(yōu)美性[J].中山大學(xué)學(xué)報：自然科學(xué)版，2007，46（4）：13-16.

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

[20]吳躍生，王廣富.非連通圖的優(yōu)美性[J].合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2013，36（8）：1010-1012.