非連通圖2C4m∪C8m－1∪G的優美標號

吳躍生

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

非連通圖2C4m∪C8m－1∪G的優美標號

吳躍生

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

討論了非連通圖2C4m∪C8m－1∪G的優美性，給出了非連通圖2C4m∪C8m－1∪G是優美圖的一個充分條件.

優美圖；平衡二分圖；非連通圖；優美標號

1 預備知識

圖的優美標號問題是圖論中一個富有挑戰性的課題［1－13］.文獻［1］已經證明：對任意正整數m，C4m和C4m－1都是優美的，而C4m＋1和C4m＋2都不是優美的.許多文獻還研究了非連通圖的優美性［2，5，13］.文獻［2］證明了非連通圖2C4m∪C8m－1是優美圖.本文討論了非連通圖2C4m∪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的優美標號.如果在集合［0，｜E（G）｜］存在整數a不是優美圖G的標號值，則稱整數a是優美圖G的優美標號的缺失值，簡稱優美圖G的缺失值.

定義2［3］G是一個優美二部圖，其優美標號為θ，V（G）劃分成兩個集合X，Y，如果，則稱θ是G的交錯標號，稱G是在交錯標號θ下的交錯圖，稱k是交錯標號θ的特征值.

定義3［4－5］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.

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

2 結果及證明

定理1 對任意正整數m，4m＋1≤k＋4m＋1≤｜E（Gk＋4m＋1）｜，非連通圖2C4m∪C8m－1∪Gk＋4m＋1存在缺失值為k＋1的優美標號.

證明 把2C4m中的一個圈記作，另一個記作，設V（）＝｛x1，x2，…，x4m｝，E（）＝｛x1x2，x2x3，…，x4m－1x4m，x4mx1｝，V）＝｛y1，y2，…，y4m｝，E（C4（2m））＝｛y1y2，y2y3，…，y4m－1y4m，y4my1｝，V（C8m－1）＝｛z1，z2，…，z8m－1｝，E（C8m－1）＝｛z1z2，z2z3，…，z8m－2z8m－1，z8m－1z1｝.設X，Y是圖Gk＋4m＋1的一個二分化，θ1是圖Gk＋4m＋1的交錯標號，且

非連通圖2C4m∪C8m－1∪Gk＋4m＋1的頂點標號θ定義為：

情況1.

θ：X→［0，k］是單射（或雙射）；θ：Y→［k＋16m，q＋16m－1］－｛20m＋k｝是單射（或雙射）.

所以，θ：V（2C4m∪C8m－1∪Gk＋4m＋1）→［0，q＋16m－1］－｛k＋1｝是單射.

情況2.

即

亦即

即

亦即

即

亦即

θ′：E（C8m－1）→［1，8m－1］是一一對應的.

θ′：E（Gk＋4m＋1）→［12m＋1，q＋12m］是一一對應的.

θ′：E（2C4m∪C8m－1∪Gk＋4m＋1）→［1，q＋16m－1］是一一對應的.

所以非連通圖2C4m∪C8m－1∪Gk＋4m＋1是優美的，θ就是其缺失值為k＋1的優美標號.

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

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

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

例1 當m＝2，n＝8，r＝0時，由推論1，非連通圖C8∪C8∪C15∪C32的缺失值為16的優美標號為：C8：46，17，45，18，43，19，42，20，46；C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C32：0，63，1，62，2，61，3，60，4，59，5，58，6，57，7，56，8，54，9，53，10，52，11，51，12，50，13，49，14，48，15，47，0.

當m＝2，n＝4，r＝1時，由推論1給出的非連通圖C8∪C8∪C15∪C16（1，1，…，1）的缺失值為16的優美標號為：

C8：46，17，45，18，43，19，42，20，46；C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C16（1，1，…，1）：0（63），62（1），2（61），60（3），4（59），58（5），6（57），56（7），8（54），53（9），10（52），51（11），12（50），49（13），14（48），47（15），0（63）.

當m＝2，n＝2，r＝3時，由推論1給出的非連通圖C8∪C8∪C15∪C8（3，3，…，3）的缺失值為16的優美標號為：

C8：46，17，45，18，43，19，42，20，46；C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C8（3，3，…，3）：0（63，62，61），60（1，2，3），4（59，58，57），56（5，6，7），8（54，53，52），51（9，10，11），12（50，49，48），47（13，14，15），0（63，62，61）.

當m＝2，n＝1，r＝4時，由推論1給出的非連通圖C8∪C8∪C15∪C4（7，7，7，7）的缺失值為16的優美標號為：

C8：46，17，45，18，43，19，42，20，46；C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C4（7，7，7，7）：0（63，62，61，60，59，58，57），56（1，2，3，4，5，6，7），8（54，53，52，51，50，49，48），47（9，10，11，12，13，14，15）.

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

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

推論2 對任意正整數m，非連通圖2C4m∪C8m－1∪2C8m存在缺失值為8m的優美標號.

例2 當m＝2時，由推論2，非連通圖2C8∪C15∪2C16的缺失值為16的優美標號為：

C8：46，17，45，18，43，19，42，20，46；

C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C16：0，63，1，62，2，61，3，60，5，59，6，58，7，57，8，56，0；

C16：54，9，53，10，52，11，51，4，50，12，49，13，48，14，47，15，54.

引理3［6］對任意正整數m，非連通圖2C4m∪C8m存在特征為8m－1且存在缺失值為12m的交錯標號.

注意到12m＝（8m－1）＋4m＋1，由定理1和引理3有下面的結論.

推論3 對任意正整數m，非連通圖2C4m∪C8m－1∪（2C4m∪C8m）存在缺失值為8m的優美標號.

例3 當m＝2時，由推論3，非連通圖2C8∪C15∪（2C8∪C16）的缺失值為16的優美標號為：

C8：46，17，45，18，43，19，42，20，46；

C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C8：0，63，1，62，2，60，3，59，0；

C8：5，58，6，61，7，57，8，56，5；

C16：54，9，53，10，52，11，51，4，50，12，49，13，48，14，47，15，54.

引理4［11］對任意自然數n，當n≥2時，C2n＋1是有2n＋1個頂點的圈，Gn－1是邊數為n－1的優美圖，則非連通圖C2n＋1∪Gn－1是優美的.

因為E（2C4m∪C8m－1）＝16m－1，由引理4有下面的結論.

推論4 設m為任意的正整數，則非連通圖（2C4m∪C8m－1）∪C2（16m）＋1是優美的.

引理5［12］當n，k為任意自然數，n≥2時，C3i（2n＋1）是有3i（2n＋1）個頂點的圈，Gn－1是邊數為n－1的優美圖，則非連通圖是優美的.

因為E（2C4m∪C8m－1）＝16m－1，由引理5有下面的結論.

推論5 設m為任意的正整數，n為任意的正整數，則非連通圖是優美的.

［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］ 吳躍生，王廣富，徐保根.非連通圖2C4m∪G的優美性［J］.煙臺大學學報：自然科學與工程版，2014，27（4）：240-243.

［7］ GALLIAN J A.A dynamic survey of graph labeling［J］.The Electronic Joumal of Combinatorics，2013，19，DS6：1-308.

［8］ 吳躍生，王廣富，徐保根.非連通圖C4m－1∪C4m∪G的優美標號［J］.西南大學學報：自然科學版，2014，36（8）：83-86.

［9］ 吳躍生，王廣富，徐保根.關于圖G∪T□K1的優美性［J］東北師大學報：自然科學版，2014，46（1）：14-16.

［10］ 吳躍生，王廣富，徐保根.非連通圖（P2∨Kn）（r1，r2，…，rn＋2）∪Gr的優美性［J］.東北師大學報：自然科學版，2014，46（3）：38-42.

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

［12］ 吳躍生.非連通圖Gn－1∪kG3i（2n＋1）的優美性［J］.河南教育學院學報，2013，22（4）：7-9.

［13］ 吳躍生，王廣富，徐保根.非連通圖3C4m∪C8m－1∪G的優美標號［J］.天津師范大學學報：自然科學版，2014，34（2）：19-23.

θ′（zz）＝8m－2i－2，i＝1，2，…，2m－1；
2i2i＋1
｛8m－2i－1，i＝2m＋1，2m＋2，…，4m－1.θ′（z4mz4m＋1）＝8m－1，θ′（z8m－1z1）＝4m－2.

The graceful labeling of the unconnected graph 2C4m∪C8m－1∪G

WU Yue-sheng
（School of Science，East China Jiaotong University，Nanchang 330013，China）

The gracefulness of the unconnected graph 2C4m∪C8m－1∪Gis discussed.One sufficient condition is given for the gracefulness of unconnected graph 2C4m∪C8m－1∪G.

graceful graph；balanced bipartite graph；unconnected graph；graceful labeling

O 157.5 ［學科代碼］ 110·7470

A

（責任編輯：陶 理）

1000-1832（2015）03-0060-04

10.16163／j.cnki.22-1123／n.2015.03.013

2013-12-17

國家自然科學基金資助項目（11261019，11361024）；江西省教育廳2014年度科學技術研究項目（GJJ14380）.

吳躍生（1959—），男，碩士，副教授，主要從事圖論研究.