非連通圖2C4（3m－1）∪C8m－1∪G 的優(yōu)美標(biāo)號

吳躍生

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

1 相關(guān)概念

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

圖的優(yōu)美標(biāo)號問題是組合數(shù)學(xué)中一個(gè)熱門課題［1－13］。文獻(xiàn)［2］已經(jīng)證明：非連通圖2C4（3m－1）∪C8m－1是優(yōu)美圖。

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

定義1［1］對于一個(gè)圖G＝（V，E），如果存在一個(gè)單射θ：V（G）→［0，｜E（G）｜］，使得對所有邊e＝（u，v）∈E（G），由θ′（e）＝｜θ（u）－θ（v）｜導(dǎo)出的E（G）→［1，｜E（G）｜］是一個(gè)雙射，則稱G是優(yōu)美圖，θ是G的一組優(yōu)美標(biāo)號，稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎo)值。

定義2［1］設(shè)f為G的一個(gè)優(yōu)美標(biāo)號，如果存在一個(gè)正整數(shù)k，使得對任意的uv∈E（G）有

成立，則稱f為G的平衡標(biāo)號（或稱G有平衡標(biāo)號f），且稱k為f的特征，圖G稱為平衡二分圖（balanced bipartite graph）。

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

定義3［1］在平衡二分圖G中，設(shè)其優(yōu)美標(biāo)號θ的特征為k，并且θ（u0）＝k，θ（v0）＝k＋1，則稱u0為G的二分點(diǎn)，v0為G的對偶二分點(diǎn)。

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

2 主要結(jié)論及其證明

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

證明 把2C4（3m－1）中 的 一 個(gè) 圈 記 作另 一 個(gè) 記設(shè)X，Y是圖G的一個(gè)二分化，θ1是圖G的交錯(cuò)標(biāo)號，且

定義2C4（3m－1）∪C8m－1∪G的頂點(diǎn)標(biāo)號θ為：

下面證 明θ是 非 連 通 圖 2C4（3m－1）∪C8m－1∪G的 優(yōu) 美標(biāo)號。

（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］是 一 一對應(yīng)。

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

引理 對任意正整數(shù)n，設(shè)C4n是有4n個(gè)頂點(diǎn)的圈，則C4n存在特征為2n－1，且缺3n的交錯(cuò)標(biāo)號。

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

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

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

推論1 對任意正整數(shù)m，非連通圖2C4（3m－1）∪C8m－1∪C48m－16存在缺標(biāo)號值24m－8的優(yōu)美標(biāo)號。

例1 由推論1，非連通圖2C8∪C7∪C32存在缺標(biāo)號值16的優(yōu)美標(biāo)號為：

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｝的每個(gè)頂點(diǎn)ui都粘接了ri條懸掛邊（ri為自然數(shù)，i＝1，2，…，n）所得到的圖，稱為圖G的（r1，r2，…，rn）－冠，簡記為G（r1，r2，…，rn）。特別地，當(dāng)r1＝r2＝…＝rn＝r時(shí)，稱為圖G的r－冠。圖G的0－冠就是圖G。

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

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

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

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

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］對任意正整數(shù)m，任意自然數(shù)r，則C4m（r，r，…，r）存在特征為2m（r＋1）－1，且缺3m（r＋1）的交錯(cuò)標(biāo)號。

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

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

例3 由推論3給出的非連通圖2C8∪C7∪C16（1，1，…，1）缺16標(biāo)號值的優(yōu)美標(biāo)號為：

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標(biāo)號值的優(yōu)美標(biāo)號為：

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標(biāo)號值的優(yōu)美標(biāo)號為：

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

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

推論4 對任意正整數(shù)m，n，當(dāng)6m－2＝n時(shí)，非連通圖2C4（3m－1）∪C8m－1∪2C4n存在缺24m－8標(biāo)號值的優(yōu)美標(biāo)號。

例4 由推論4給出的非連通圖2C8∪C7∪2C16缺16標(biāo)號值的優(yōu)美標(biāo)號為：

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］對任意正整數(shù)m（m≠3），mC4存在特征為2m－1，且缺3m的交錯(cuò)標(biāo)號。

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

推論5 對任意正整數(shù)m，n，當(dāng)12m－1＝n時(shí)，非連通圖2C4（3m－1）∪C8m－1∪nC4存 在 缺 24m－8 標(biāo) 號 值 的 優(yōu) 美標(biāo)號。

例5 由推論5給出的非連通圖2C8∪C7∪8C4缺16標(biāo)號值的優(yōu)美標(biāo)號為：

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］馬克杰.優(yōu)美圖［M］.北京：北京大學(xué)出版社，1991：1－247.

［2］董俊超.C4k∪C4k∪Cm的優(yōu)美性［J］.煙臺大學(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］吳躍生.關(guān)于圖P6k＋53∪Pn3的優(yōu)美性［J］.吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，33（3）：4－7.

［7］吳躍生，徐保根.兩類非連通圖（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.

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

［9］吳躍生，王廣富，徐保根.關(guān)于C4h＋1⊙K1的（Gr1，Gr2，…，Gr4h＋1，Gr4h＋2）－冠 的 優(yōu) 美 性 ［J］.山 東 大 學(xué) 學(xué) 報(bào)，2013，48（4）：25－27.

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

［11］吳躍生，王廣富，徐保根.非連通圖C2n＋1∪Gn－1的優(yōu)美性［J］.華東交通大學(xué)學(xué)報(bào)，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.