非連通圖2C4m∪C8m－1∪G的優(yōu)美標(biāo)號(hào)

吳躍生

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

非連通圖2C4m∪C8m－1∪G的優(yōu)美標(biāo)號(hào)

吳躍生

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

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

優(yōu)美圖；平衡二分圖；非連通圖；優(yōu)美標(biāo)號(hào)

1 預(yù)備知識(shí)

圖的優(yōu)美標(biāo)號(hào)問(wèn)題是圖論中一個(gè)富有挑戰(zhàn)性的課題［1－13］.文獻(xiàn)［1］已經(jīng)證明：對(duì)任意正整數(shù)m，C4m和C4m－1都是優(yōu)美的，而C4m＋1和C4m＋2都不是優(yōu)美的.許多文獻(xiàn)還研究了非連通圖的優(yōu)美性［2，5，13］.文獻(xiàn)［2］證明了非連通圖2C4m∪C8m－1是優(yōu)美圖.本文討論了非連通圖2C4m∪C8m－1∪G的優(yōu)美性.

定義1［1］對(duì)于一個(gè)圖G＝（V，E），如果存在一個(gè)單射θ：V（G）→［0，｜E（G）｜］，使得對(duì)所有邊e＝（u，v）∈E（G），由θ′（e）＝｜θ（u）－θ（v）｜導(dǎo)出的映射θ′：E（G）→［1，｜E（G）｜］是一一對(duì)應(yīng)的，則稱圖G是優(yōu)美圖，稱θ是圖G的優(yōu)美標(biāo)號(hào).如果在集合［0，｜E（G）｜］存在整數(shù)a不是優(yōu)美圖G的標(biāo)號(hào)值，則稱整數(shù)a是優(yōu)美圖G的優(yōu)美標(biāo)號(hào)的缺失值，簡(jiǎn)稱優(yōu)美圖G的缺失值.

定義2［3］G是一個(gè)優(yōu)美二部圖，其優(yōu)美標(biāo)號(hào)為θ，V（G）劃分成兩個(gè)集合X，Y，如果，則稱θ是G的交錯(cuò)標(biāo)號(hào)，稱G是在交錯(cuò)標(biāo)號(hào)θ下的交錯(cuò)圖，稱k是交錯(cuò)標(biāo)號(hào)θ的特征值.

定義3［4－5］V（G）＝｛u1，u2，…，un｝的每個(gè)頂點(diǎn)ui都粘接了ri條懸掛邊（ri為自然數(shù)，i＝1，2，…，n）所得到的圖，稱為圖G的（r1，r2，…，rn）-冠，簡(jiǎn)記為G（r1，r2，…，rn）.特別的，當(dāng)r1＝r2＝…＝rn＝r時(shí)，稱其為圖G的r-冠.圖G的0-冠就是圖G.

本文所討論的圖均為無(wú)向簡(jiǎn)單圖，V（G）和E（G）分別表示圖G的頂點(diǎn)集和邊集.記號(hào)Gk＋m表示圖G是特征為k且缺失值為k＋m的交錯(cuò)圖.記號(hào)［m，n］表示整數(shù)集合｛m，m＋1，…，n｝，其中m和n均為非負(fù)整數(shù)，且滿足0≤m＜n.未說(shuō)明的符號(hào)及術(shù)語(yǔ)均同文獻(xiàn)［1］.

2 結(jié)果及證明

定理1 對(duì)任意正整數(shù)m，4m＋1≤k＋4m＋1≤｜E（Gk＋4m＋1）｜，非連通圖2C4m∪C8m－1∪Gk＋4m＋1存在缺失值為k＋1的優(yōu)美標(biāo)號(hào).

證明 把2C4m中的一個(gè)圈記作，另一個(gè)記作，設(shè)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｝.設(shè)X，Y是圖Gk＋4m＋1的一個(gè)二分化，θ1是圖Gk＋4m＋1的交錯(cuò)標(biāo)號(hào)，且

非連通圖2C4m∪C8m－1∪Gk＋4m＋1的頂點(diǎn)標(biāo)號(hào)θ定義為：

情況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］是一一對(duì)應(yīng)的.

θ′：E（Gk＋4m＋1）→［12m＋1，q＋12m］是一一對(duì)應(yīng)的.

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

所以非連通圖2C4m∪C8m－1∪Gk＋4m＋1是優(yōu)美的，θ就是其缺失值為k＋1的優(yōu)美標(biāo)號(hào).

引理1［4］對(duì)任意正整數(shù)m，任意自然數(shù)r，C4m（r，r，…，r）存在特征為2m（r＋1）－1，且缺失值為3m（r＋1）的交錯(cuò)標(biāo)號(hào).

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

推論1 對(duì)任意正整數(shù)m，n，任意自然數(shù)r，當(dāng)4m＝n（r＋1）時(shí)，非連通圖2C4m∪C8m－1∪C4n（r，r，…，r）存在缺失值為2n（r＋1）的優(yōu)美標(biāo)號(hào).

例1 當(dāng)m＝2，n＝8，r＝0時(shí)，由推論1，非連通圖C8∪C8∪C15∪C32的缺失值為16的優(yōu)美標(biāo)號(hào)為：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.

當(dāng)m＝2，n＝4，r＝1時(shí)，由推論1給出的非連通圖C8∪C8∪C15∪C16（1，1，…，1）的缺失值為16的優(yōu)美標(biāo)號(hào)為：

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

當(dāng)m＝2，n＝2，r＝3時(shí)，由推論1給出的非連通圖C8∪C8∪C15∪C8（3，3，…，3）的缺失值為16的優(yōu)美標(biāo)號(hào)為：

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

當(dāng)m＝2，n＝1，r＝4時(shí)，由推論1給出的非連通圖C8∪C8∪C15∪C4（7，7，7，7）的缺失值為16的優(yōu)美標(biāo)號(hào)為：

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］對(duì)任意正整數(shù)m，2C4m存在特征為4m－1，且缺失值為6m的交錯(cuò)標(biāo)號(hào).

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

推論2 對(duì)任意正整數(shù)m，非連通圖2C4m∪C8m－1∪2C8m存在缺失值為8m的優(yōu)美標(biāo)號(hào).

例2 當(dāng)m＝2時(shí)，由推論2，非連通圖2C8∪C15∪2C16的缺失值為16的優(yōu)美標(biāo)號(hào)為：

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］對(duì)任意正整數(shù)m，非連通圖2C4m∪C8m存在特征為8m－1且存在缺失值為12m的交錯(cuò)標(biāo)號(hào).

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

推論3 對(duì)任意正整數(shù)m，非連通圖2C4m∪C8m－1∪（2C4m∪C8m）存在缺失值為8m的優(yōu)美標(biāo)號(hào).

例3 當(dāng)m＝2時(shí)，由推論3，非連通圖2C8∪C15∪（2C8∪C16）的缺失值為16的優(yōu)美標(biāo)號(hào)為：

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］對(duì)任意自然數(shù)n，當(dāng)n≥2時(shí)，C2n＋1是有2n＋1個(gè)頂點(diǎn)的圈，Gn－1是邊數(shù)為n－1的優(yōu)美圖，則非連通圖C2n＋1∪Gn－1是優(yōu)美的.

因?yàn)镋（2C4m∪C8m－1）＝16m－1，由引理4有下面的結(jié)論.

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

引理5［12］當(dāng)n，k為任意自然數(shù)，n≥2時(shí)，C3i（2n＋1）是有3i（2n＋1）個(gè)頂點(diǎn)的圈，Gn－1是邊數(shù)為n－1的優(yōu)美圖，則非連通圖是優(yōu)美的.

因?yàn)镋（2C4m∪C8m－1）＝16m－1，由引理5有下面的結(jié)論.

推論5 設(shè)m為任意的正整數(shù)，n為任意的正整數(shù)，則非連通圖是優(yōu)美的.

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

［2］ 董俊超.C4k∪C4k∪Cm的優(yōu)美性［J］.煙臺(tái)大學(xué)學(xué)報(bào)：自然科學(xué)與工程版，1999，12（4）：238-241.

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

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

［5］ 吳躍生，李詠秋.關(guān)于圈C4h＋3的（r1，r2，…，r4h＋3）-冠的優(yōu)美性［J］.吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，32（6）：1-4.

［6］ 吳躍生，王廣富，徐保根.非連通圖2C4m∪G的優(yōu)美性［J］.煙臺(tái)大學(xué)學(xué)報(bào)：自然科學(xué)與工程版，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的優(yōu)美標(biāo)號(hào)［J］.西南大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，36（8）：83-86.

［9］ 吳躍生，王廣富，徐保根.關(guān)于圖G∪T□K1的優(yōu)美性［J］東北師大學(xué)報(bào)：自然科學(xué)版，2014，46（1）：14-16.

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

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

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

［13］ 吳躍生，王廣富，徐保根.非連通圖3C4m∪C8m－1∪G的優(yōu)美標(biāo)號(hào)［J］.天津師范大學(xué)學(xué)報(bào)：自然科學(xué)版，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 ［學(xué)科代碼］ 110·7470

A

（責(zé)任編輯：陶 理）

1000-1832（2015）03-0060-04

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

2013-12-17

國(guó)家自然科學(xué)基金資助項(xiàng)目（11261019，11361024）；江西省教育廳2014年度科學(xué)技術(shù)研究項(xiàng)目（GJJ14380）.

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