非連通圖2C4（3m－1）∪C8m－1∪G 的優美標號

吳躍生

（華東交通大學 理學院，南昌330013）

1 相關概念

本文所討論的圖均為無向簡單圖，V（G）和E（G）分別表示圖G的頂點集和邊集，記號［m，n］表示整數集合｛m，m＋1，…，n｝，其中m和n均為非負整數，且滿足0≤m＜n。未說明的符號及術語均同文獻［1］。

圖的優美標號問題是組合數學中一個熱門課題［1－13］。文獻［2］已經證明：非連通圖2C4（3m－1）∪C8m－1是優美圖。

本文擬討論非連通圖2C4（3m－1）∪C8m－1∪G的優美性。

定義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為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［3］G是一個優美二部圖，其優美標號為θ，V（G）劃分成兩個集合X，Y，如果則稱θ是G的交錯標號，稱G是在交錯標號θ下的交錯圖。

2 主要結論及其證明

定理 對任意正整數m，如果圖G是特征為k且缺k＋12m－3標號值的交錯圖（12m－3≤k＋12m－3≤｜E（G）｜），非連通圖2C4（3m－1）∪C8m－1∪G存在缺標號值k＋1的優美標號。

證明 把2C4（3m－1）中 的 一 個 圈 記 作另 一 個 記設X，Y是圖G的一個二分化，θ1是圖G的交錯標號，且

定義2C4（3m－1）∪C8m－1∪G的頂點標號θ為：

下面證 明θ是 非 連 通 圖 2C4（3m－1）∪C8m－1∪G的 優 美標號。

（1）θ：X→［0，k］是單射（或雙射）；θ：Y→［k＋32m－8，q＋32m－9］－｛44m＋k－12｝是單射（或雙射）；

θ：→［k＋2，6m＋k－1］∪［26m＋k－7，32m＋k－9］－｛29m＋k－8｝是單射（或雙射）；

θ：V（）→［6m＋k＋1，12m＋k－2］∪［20m＋k－3，26m＋k－8］－｛29m＋k－8，44m＋k－12｝是單射（或雙射）；

θ：V（C）→［12m＋k－1，20m＋k－4］∪｛6m＋k｝是單射（或雙射）；

θ：V（2C4（3m－1）∪C8m－1∪G）→［0，q＋32m－9］－｛k＋1｝是單射。

（2）θ′：E（）→［20m－6，32m－11］是雙射；

θ′：E（）→［8m，20m－7］∪｛32m－10，32m－9｝是雙射；

θ′：E（C8m－1）→［1，8m－1］是雙射；

θ′：E（G）→［32m－8，q＋32m－9］是雙射；

θ′：E（2C4（3m－1）∪C8m－1∪G）→ ［1，q＋32m－9］是 一 一對應。

由（1）和（2）可知θ就是非連通圖2C4（3m－1）∪C8m－1∪G的缺k＋1標號值的優美標號。

引理 對任意正整數n，設C4n是有4n個頂點的圈，則C4n存在特征為2n－1，且缺3n的交錯標號。

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

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

注意到：3n＝（2n－1）＋n＋1，由定理和引理1有以下推論。

推論1 對任意正整數m，非連通圖2C4（3m－1）∪C8m－1∪C48m－16存在缺標號值24m－8的優美標號。

例1 由推論1，非連通圖2C8∪C7∪C32存在缺標號值16的優美標號為：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0，55 ，1，54，2，53，3，52，4，51，5，50，6，49，7，48，8，46，9，45，10，44，11，43，12，42，13，41，14，40，15，39.

定義5［3－4］V（G）＝｛u1，u2，…，un｝的每個頂點ui都粘接了ri條懸掛邊（ri為自然數，i＝1，2，…，n）所得到的圖，稱為圖G的（r1，r2，…，rn）－冠，簡記為G（r1，r2，…，rn）。特別地，當r1＝r2＝…＝rn＝r時，稱為圖G的r－冠。圖G的0－冠就是圖G。

引理2［3］對任意正整數m，任意自然數r1，r2，…，rm，則C4m（r1，0，r2，0，…，rm，0，…，0）存在特征為2m－1，且缺3m的交錯標號。

注意到：3m＝（2m－1）＋m＋1，由定理和引理2有下面的推論。

推論2 對任意正整數m，任意自然數r1，r2，…，r12m－4，非連通圖2C4（3m－1）∪C8m－1∪C48m－16（r1，0，r2，0，…，r12m－4，0，0，…，0）存在缺標號值24m－8的優美標號。

例2 由推論2，非連通圖2C8∪C7∪C32（1，0，2，0，3，0，4，0，5，0，6，0，7，0，8，0，0，…，0）存在缺標號值16的優美標號為：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0（91），90，1（89，88），87，2（86，85，84），83，3（82，81，80，79），78，4（77，76，75，74，73），72，5（71，70，69，68，67，66），65，6（64，63，62，61，60，59，58），57，7（56，55，54，53，52，51，50，49），48，8，46，9，45，10，44，11，43，12，42，13，41，14，40，15，39.

引理3［3］對任意正整數m，任意自然數r，則C4m（r，r，…，r）存在特征為2m（r＋1）－1，且缺3m（r＋1）的交錯標號。

注意到：3m（r＋1）＝（2m（r＋1）－1）＋m（r＋1）＋1，由定理和引理3有下面的推論。

推論3 對任意正整數m，n，任意自然數r，當12m－4＝n（r＋1）時，非連通圖2C4（3m－1）∪C8m－1∪C4n（r，r，…，r）存在缺2n（r＋1）標號值的優美標號。

例3 由推論3給出的非連通圖2C8∪C7∪C16（1，1，…，1）缺16標號值的優美標號為：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0（55），54（1），2（53），52（3），4（51），50（5），6（49），48（7），8（46），45（9），10（44），43（11），12（42），41（13），14（40），39（15）.

由推論3給出的非連通圖2C8∪C7∪C8（3，3，…，3）缺16標號值的優美標號為：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0（55 ，54，53），52（1，2，3），4（51，50，49），48（5，6，7），8（46，45，44），43（9，10，11），12（42，41，40），39（13，14，15）.

由推論3給出的非連通圖2C8∪C7∪C4（7，7，7，7）缺16標號值的優美標號為：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0（55 ，54，53，52，51，50，49），48（1，2，3，4，5，6，7），8（46，45，44，43，42，41，40），39（9，10，11，12，13，14，15）.

引理4［1］對任意正整數m，2C4m存在特征為4m－1，且缺6m的交錯標號。

注意到：6m＝（4m－1）＋2m＋1，由定理和引理4有下面的推論。

推論4 對任意正整數m，n，當6m－2＝n時，非連通圖2C4（3m－1）∪C8m－1∪2C4n存在缺24m－8標號值的優美標號。

例4 由推論4給出的非連通圖2C8∪C7∪2C16缺16標號值的優美標號為：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0，55 ，1，54，2，53，3，52，5，51，6，50，7，49，8，48；

46，9 ，45，10，44，11，43.4.42，12，41.13，40，14，39，15.

引理5［13］對任意正整數m（m≠3），mC4存在特征為2m－1，且缺3m的交錯標號。

注意到：3m＝（2m－1）＋m＋1，由定理和引理5有下面的推論。

推論5 對任意正整數m，n，當12m－1＝n時，非連通圖2C4（3m－1）∪C8m－1∪nC4存 在 缺 24m－8 標 號 值 的 優 美標號。

例5 由推論5給出的非連通圖2C8∪C7∪8C4缺16標號值的優美標號為：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

55，0 ，53，1；54，3，48，5；52，2，50，6；51，4，43，11；

49，7 ，45，8；46，10，40，12；44，9，42，13；41，14，39，15.

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

［2］董俊超.C4k∪C4k∪Cm的優美性［J］.煙臺大學學報：自然科學與工程版，1999，12（4）：238－241.

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

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

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

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

［7］吳躍生，徐保根.兩類非連通圖（P2∨珡Kn）（0，0，r1，0，…，0，rn）∪St（m）及（P2∨珡Kn）（r1＋a，r2，0，…，0）∪Gr的優美性［J］.中山大學學報：自然科學版，2012，51（5）：63－66.

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

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

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

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

［12］Gallian J A.A dynamic survey of graph labeling［J］.The Electronic Joumal of Combinatorics，2012，19，DS6：1－260.

［13］Jaromir Abrham，Anton Kotzig.All 2－regular graphs consisting of 4－cycles are graceful［J］.Discrete Mathematics，1994，135（1－3）：1－14.