吳躍生

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

1 引言與概念

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

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

文獻(xiàn)［14］討論了非連通圖2C4（3m－1）∪C8m－1∪G 的優(yōu)美性，給出了非連通圖2C4（3m－1）∪C8m－1∪G 是優(yōu)美圖的一個(gè)充分條件：對(duì)任意正整數(shù)m，如果圖G是特征為k且缺k＋12m－3標(biāo)號(hào)值的交錯(cuò)圖（12 m－3≤k＋12 m－3≤｜E（G）｜），則非連通圖2C4（3m－1）∪C8m－1∪G 存在缺標(biāo)號(hào)值k＋1的優(yōu)美標(biāo)號(hào)。

本文將繼續(xù)討論非連通圖2C4（3m－1）∪C8m－1∪G 的優(yōu)美性，給出非連通圖2C4（3m－1）∪C8m－1∪G 是優(yōu)美圖的另外5個(gè)充分條件。

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

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

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

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

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

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

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

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

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

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

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

類(lèi)似定理1的證明，可以證明θ就是非連通圖2C4（3m－1）∪C8m－1∪G的缺k＋32 m－9標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

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

類(lèi)似定理1的證明，可以證明θ就是非連通圖2C4（3m－1）∪C8m－1∪G的缺k＋1標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

證明 把2C4（3m－1）中的 一 個(gè) 圈 記 作，另 一 個(gè) 記作，設(shè)V（）＝ ｛x1，x2，…，x4（3m－1）｝，）＝ ｛x1x2，x2x3，…，x12m－5x12m－4，x12m－4x1｝，V（）＝｛y1，y2，…，y12m－4｝，E（）＝｛y1y2，y2y3，…，y12m－5y12m－4，y12m－4y1｝，V（C8m－1）＝ ｛z1，z2，…，z8m－1｝，E（C8m－1）＝｛z1z2，z2z3，…，z8m－2z8m－1，z8m－1z1｝，設(shè) X，Y 是圖G的一個(gè)二分化，θ1是圖G的交錯(cuò)標(biāo)號(hào)，且（v）＝k＜（v）＝k＋1，｜E（G）｜＝q。

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

類(lèi)似定理1的證明，可以證明θ就是非連通圖2C4（3m－1）∪C8m－1∪G的缺k＋20 m－5標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

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

類(lèi)似定理1的證明，可以證明θ就是非連通圖2C4（3m－1）∪C8m－1∪G的缺k＋12 m－4標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

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

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

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

例1 由推論，當(dāng)m＝1，n＝18，r＝0時(shí)，非連通圖2C8∪C7∪C72存在缺標(biāo)號(hào)值50的優(yōu)美標(biāo)號(hào)為：

由推論，當(dāng)m＝1，n＝9，r＝1時(shí)，非連通圖2C8∪C7∪C36（1，1，…，1）存在缺標(biāo)號(hào)值50的優(yōu)美標(biāo)號(hào)為：

由推論，當(dāng)m＝1，n＝6，r＝2時(shí)，非連通圖2C8∪C7∪C24（2，2，…，2）存在缺標(biāo)號(hào)值50的優(yōu)美標(biāo)號(hào)為：

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

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

由推論，當(dāng)m＝1，n＝1，r＝17時(shí)，非連通圖2C8∪C7∪C4（17，17，17，17）存在缺標(biāo)號(hào)值50的優(yōu)美標(biāo)號(hào)為：

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

［7］ 吳躍生，徐保根.兩類(lèi)非連通圖（P2）（0，0，r1，0，…，0，rn）∪St（m）及（P2）（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）∪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，2007，16（DS6）：1－58.

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

［14］ 吳躍生.非連通圖2C4（3m－1）∪C8m－1∪G 的優(yōu)美標(biāo)號(hào)［J］.唐山學(xué)院學(xué)報(bào)，2014，27（3）：12－14.

［15］ 吳躍生.非連通圖 G＋e∪Hk－1的優(yōu)美性［J］.吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，35（2）：3－5.

［16］ 吳躍生.非連通圖C4m－1∪G的優(yōu)美標(biāo)號(hào)［J］.吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，35（3）：1－3.

［17］ 賈慧羨，左大偉.與扇圖相關(guān)的2類(lèi)圖的超邊優(yōu)美標(biāo)號(hào)［J］.吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，35（2）：6－9.