非連通圖（P1∨Pm）∪C4n∪P2的優(yōu)美性

吳躍生，王廣富，徐保根

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

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

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

本文所討論的圖均為無(wú)向簡(jiǎn)單圖，V（G）和E（G）分別表示圖G的頂點(diǎn)集和邊集，未說(shuō)明的符號(hào)及術(shù)語(yǔ)均同文獻(xiàn)[1].

定義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 是優(yōu)美圖，稱θ是G的一組優(yōu)美標(biāo)號(hào)，稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎo)值.

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

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

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

成立，則稱θ為G的平衡標(biāo)號(hào)（或稱G有平衡標(biāo)號(hào)θ），且稱k為θ的特征.圖G稱為平衡二分圖.

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

由定義3和定義4知：平衡圖與交錯(cuò)圖等價(jià)，平衡圖的平衡標(biāo)號(hào)θ的特征

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

2 主要結(jié)果

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

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

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

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

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

（2）非連通圖G∪H∪P2中H的頂點(diǎn)標(biāo)號(hào)集合是{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)出標(biāo)號(hào)集合是{n+2，n+3，…，m+n}.

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

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

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

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

證明 記 P1和 Pn上的頂點(diǎn)依次為 v0和 v1，v2，…，vn，定義P1∨Pn的第1種頂點(diǎn)標(biāo)號(hào)θ為：

θ（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ù)容易驗(yàn)證，θ是P1∨Pn的優(yōu)美標(biāo)號(hào)，且缺標(biāo)號(hào)值2，4，…，2n-2.定義 θ：

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

定義P1∨Pn的第2種頂點(diǎn)標(biāo)號(hào)θ為：

θ（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ù)

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

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

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

引理4 設(shè)C4n是4n個(gè)頂點(diǎn)的圈，則C4n存在特征為2n-1，且缺3n的交錯(cuò)標(biāo)號(hào).

證明 記圈C4n上的頂點(diǎn)依次為v1，v2，…，v4n，定義圈C4n的頂點(diǎn)標(biāo)號(hào)θ為

容易驗(yàn)證，θ就是圈C4n的特征為2n-1，且缺3n的交錯(cuò)標(biāo)號(hào).

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

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

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

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

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

（P1∨P5）∪C20∪P2的優(yōu)美標(biāo)號(hào)：P1的標(biāo)號(hào)為 19；P5上各點(diǎn)的標(biāo)號(hào)依次為 10，18，12，16，14；C20上各點(diǎn)的標(biāo)號(hào)依次為 0，30，1，29，2，28，3，27，4，26，5，24，6，23，7，22，8，21，9，20；P2上各點(diǎn)的標(biāo)號(hào)依次為 15，25.注：（P1∨P5）的優(yōu)美標(biāo)號(hào)：P1的標(biāo)號(hào)為9；P5上各點(diǎn)的標(biāo)號(hào)依次為 0，8，2，6，4；C20上缺標(biāo)號(hào)值15的各點(diǎn)的優(yōu)美標(biāo)號(hào)依次為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)美標(biāo)號(hào)：P1的標(biāo)號(hào)為 23；P5上各點(diǎn)的標(biāo)號(hào)依次為 14，22，16，20，18；C28上各點(diǎn)的標(biāo)號(hào)依次為 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上各點(diǎn)的標(biāo)號(hào)依次為 21，31.注：（P1∨P5）的優(yōu)美標(biāo)號(hào)：P1的標(biāo)號(hào)為9；P5上各點(diǎn)的標(biāo)號(hào)依次為 0，8，2，6，4；C28上缺標(biāo)號(hào)值 21的各點(diǎn)的優(yōu)美標(biāo)號(hào)依次為 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)美標(biāo)號(hào)：P1的標(biāo)號(hào)為 4；P5上各點(diǎn)的標(biāo)號(hào)依次為13，5，11，7，9；C8上各點(diǎn)的標(biāo)號(hào)依次為 0，18，1，17，2，15，3，14；P2上各點(diǎn)的標(biāo)號(hào)依次為 6，16.注：（P1∨P5）的優(yōu)美標(biāo)號(hào)：P1的標(biāo)號(hào)為 0；P5上各點(diǎn)的標(biāo)號(hào)依次為 9，1，7，3，5；C8上缺標(biāo)號(hào)值6的各點(diǎn)的優(yōu)美標(biāo)號(hào)依次為0，8，1，7，2，5，3，4.

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

（P1∨P5）∪C24∪P2的優(yōu)美標(biāo)號(hào)：P1的標(biāo)號(hào)為 12；P5上各點(diǎn)的標(biāo)號(hào)依次為 21，13，19，15，17；C24上各點(diǎn)的標(biāo)號(hào)依次為 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上各點(diǎn)的標(biāo)號(hào)依次為 18，28.注：（P1∨P5）的優(yōu)美標(biāo)號(hào)：P1的標(biāo)號(hào)為0；P5上各點(diǎn)的標(biāo)號(hào)依次為9，1，7，3，5；C24上缺標(biāo)號(hào)值18的各點(diǎn)的優(yōu)美標(biāo)號(hào)依次為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)美標(biāo)號(hào)：P1的標(biāo)號(hào)為 16；P5上各點(diǎn)的標(biāo)號(hào)依次為 25，17，23，19，21；C32上各點(diǎn)的標(biāo)號(hào)依次為 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上各點(diǎn)的標(biāo)號(hào)依次為 24，34.注：（P1∨P5）的優(yōu)美標(biāo)號(hào)：P1的標(biāo)號(hào)為 0；P5上各點(diǎn)的標(biāo)號(hào)依次為9，1，7，3，5；C32上缺標(biāo)號(hào)值24的各點(diǎn)的優(yōu)美標(biāo)號(hào)依次為 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)美標(biāo)號(hào)如下：

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

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

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

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

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

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

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

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

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

[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.

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

[10]張志尚，王春月，張慶成.關(guān)于wn∪wn∪Pm的優(yōu)美性[J].東北師范大學(xué)學(xué)報(bào)：自然科學(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é)報(bào)：自然科學(xué)版，2012，51（5）：63-66.

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

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

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

[16]吳躍生，王廣富，徐保根.非連通圖C2n+1∪Gn-1的優(yōu)美性[J].華東交通大學(xué)學(xué)報(bào)，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é)報(bào)：自然科學(xué)版，2007，46（4）：13-16.

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

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