再探非連通圖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－14］。文獻［2］已經證明非連通圖2C4（3m－1）∪C8m－1是優美圖。

文獻［14］討論了非連通圖2C4（3m－1）∪C8m－1∪G 的優美性，給出了非連通圖2C4（3m－1）∪C8m－1∪G 是優美圖的一個充分條件：對任意正整數m，如果圖G是特征為k且缺k＋12m－3標號值的交錯圖（12 m－3≤k＋12 m－3≤｜E（G）｜），則非連通圖2C4（3m－1）∪C8m－1∪G 存在缺標號值k＋1的優美標號。

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

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

2 主要結論及其證明

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

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

（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］是 一 一對應。

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

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

類似定理1的證明，可以證明θ就是非連通圖2C4（3m－1）∪C8m－1∪G的缺k＋32 m－9標號值的優美標號。

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

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

類似定理1的證明，可以證明θ就是非連通圖2C4（3m－1）∪C8m－1∪G的缺k＋1標號值的優美標號。

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

證明 把2C4（3m－1）中的 一 個 圈 記 作，另 一 個 記作，設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｝，設 X，Y 是圖G的一個二分化，θ1是圖G的交錯標號，且（v）＝k＜（v）＝k＋1，｜E（G）｜＝q。

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

類似定理1的證明，可以證明θ就是非連通圖2C4（3m－1）∪C8m－1∪G的缺k＋20 m－5標號值的優美標號。

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

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

類似定理1的證明，可以證明θ就是非連通圖2C4（3m－1）∪C8m－1∪G的缺k＋12 m－4標號值的優美標號。

定義2［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。

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

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

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

例1 由推論，當m＝1，n＝18，r＝0時，非連通圖2C8∪C7∪C72存在缺標號值50的優美標號為：

由推論，當m＝1，n＝9，r＝1時，非連通圖2C8∪C7∪C36（1，1，…，1）存在缺標號值50的優美標號為：

由推論，當m＝1，n＝6，r＝2時，非連通圖2C8∪C7∪C24（2，2，…，2）存在缺標號值50的優美標號為：

由推論，當m＝1，n＝3，r＝5時，非連通圖2C8∪C7∪C12（5，5，…，5）存在缺標號值50的優美標號為：

由推論，當m＝1，n＝2，r＝8時，非連通圖2C8∪C7∪C8（8，8，…，8）存在缺標號值50的優美標號為：

由推論，當m＝1，n＝1，r＝17時，非連通圖2C8∪C7∪C4（17，17，17，17）存在缺標號值50的優美標號為：

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

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

［8］ 吳躍生.圖 C7（r1，r2，r3，r4，r5，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，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 的優美標號［J］.唐山學院學報，2014，27（3）：12－14.

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

［16］ 吳躍生.非連通圖C4m－1∪G的優美標號［J］.吉首大學學報：自然科學版，2014，35（3）：1－3.

［17］ 賈慧羨，左大偉.與扇圖相關的2類圖的超邊優美標號［J］.吉首大學學報：自然科學版，2014，35（2）：6－9.