非連通圖2C4m∪G是優美圖的5個充分條件

吳躍生

(華東交通大學 理學院，南昌 330013)

非連通圖2C4m∪G是優美圖的5個充分條件

吳躍生

(華東交通大學 理學院，南昌 330013)

討論了非連通圖2C4m∪G的優美性，給出了非連通圖2C4m∪G是優美圖的5個充分條件。

優美圖；交錯圖；非連通圖；優美標號

1 相關概念

圖的優美標號問題是組合數學中的一個熱門課題。

定義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的一組優美標號。

本文所討論的圖均為無向簡單圖，V(G)和E(G)分別表示圖G的頂點集和邊集。記號Gk+m表示圖G是特征為k且缺k+m標號值的交錯圖。記號[m，n]表示整數集合{m，m+1，…，n}，其中m和n均為非負整數，且滿足0≤m

文獻[1]已經證明了非連通圖2C4m是優美圖。文獻[2]研究了非連通圖2C4m∪Cn的優美性，證明了非連通圖2C4m∪C8m-1，2C4(3m-1)∪C8m-1和2C4(3m+1)∪C4(2m+1)是優美圖。文獻[3]討論了非連通圖2C4m∪G的優美性，給出了非連通圖2C4m∪G是優美圖的一個充分條件：對任意正整數m，設G是特征為k，且缺k+2m+1標號值的交錯圖，則非連通圖2C4m∪G存在特征為4m+k+1，且缺k+1標號值的交錯標號(2m+1≤k+2m+1≤|E(G)|)。

本文繼續討論非連通圖2C4m∪G的優美性，給出非連通圖2C4m∪G的是優美圖的五個充分條件。

2 主要結論及其證明

定理1 對任意正整數m，如果2m≤k+2m≤|E(G)|，則非連通圖2C4m∪Gk+2m存在特征為4m+k，且缺k+8m標號值的交錯標號。

把非連通圖2C4m∪Gk+2m的頂點標號θ定義為：

θ(x2i)=2m+i+k+1，i=1，2，…，m-1；

θ(x2m)=m+k+1，θ(x2i)=2m+i+k，i=m+1，m+2，…，2m；

θ(x2i-1)=6m-i+k+1，i=1，2，…，2m；

θ(y2i-1)=8m-i+k，i=1，2，…，2m-1；

θ(y4m-1)=k+10m。

θ：X→[0，k]是單射(或雙射)；θ：Y→[k+8m+1，q+8m]-{k+10m}是單射；

因而，映射θ：V(2C4m∪Gk+2m)→[0，q+8m]-{k+8m}是單射。

θ′(x2m-1x2m)=4m，

θ′(x2mx2m+1)=4m-1，θ′(x4mx1)=2m，

θ′(y4m-1y4m)=8m-1，

θ′(y4m-2y4m-1)=8m，θ′(y4my1)=6m-2，

θ′：E(Gk+2m)→[8m+1，q+8m]是雙射。

因而，映射θ′：E(2C4m∪Gk+2m)→[1，q+8m]一一對應，所以θ就是非連通圖2C4m∪Gk+2m的缺k+8m標號值的優美標號。

所以，θ就是非連通圖2C4m∪Gk+2m的特征為4m+k，且缺k+8m標號值的交錯標號。證畢。

定理2 對任意正整數m，如果6m-1≤k+6m-1≤|E(G)|，則非連通圖2C4m∪Gk+6m-1存在缺k+8m標號值的優美標號。

定義非連通圖2C4m∪Gk+6m-1的頂點標號θ為：

θ(x2i)=6m-i+k-1，i=1，2，…，m-1；

θ(x2m)=7m+k-1，

θ(x2i)=6m-i+k，i=m+1，m+2，…，2m；

θ(x2i-1)=2m+i+k-1，i=1，2，…，2m；

θ(y2i-1)=i+k，i=1，2，…，2m-1；

θ(y4m-1)=k+14m-1。

順應論視角下的美劇字幕翻 譯 ………………………………………………………………………… 安 紅（62）

θ：X→[0，k]是單射(或雙射)；θ：Y→[k+8m+1，q+8m]-{k+14m-1}是單射；

因而，映射θ：V(2C4m∪Gk+6m-1)→[0，q+8m]-{k+8m}是單射。

θ′：E(Gk+6m-1)→[8m+1，q+8m]是雙射。

因而，映射θ′：E(2C4m∪Gk+6m-1)→[1，q+8m]一一對應，θ就是非連通圖2C4m∪Gk+6m-1的缺k+8m標號值的優美標號。

定理3 對任意正整數m，如果6m≤k+6m≤|E(G)|，則非連通圖2C4m∪Gk+6m存在缺k+1標號值的優美標號。

定義非連通圖2C4m∪Gk+6m的頂點標號θ為：

θ(x2i)=6m-i+k，i=1，2，…，m-1；

θ(x2m)=7m+k，

θ(x2i)=6m-i+k+1，i=m+1，m+2，…，2m；

θ(x2i-1)=2m+i+k，i=1，2，…，2m；

θ(y2i-1)=i+k+1，i=1，2，…，2m-1；

θ(y4m-1)=k+14m。

θ：X→[0，k]是單射(或雙射)；θ：Y→[k+8m+1，q+8m]-{k+14m}是單射；

因而，映射θ：V(2C4m∪Gk+6m)→[0，q+8m]-{k+1}是單射。

θ′：E(Gk+6m)→[8m+1，q+8m]是雙射。

因而，映射θ′：E(2C4m∪Gk+6m)→[1，q+8m]一一對應，θ就是非連通圖2C4m∪Gk+6m的缺k+1標號值的優美標號。

定理4 對任意正整數m，如果6m≤k+6m≤|E(G)|，則非連通圖2C4m∪Gk+6m存在缺k+2m標號值的優美標號。

定義非連通圖2C4m∪Gk+6m的頂點標號θ為：

θ：X→[0，k]是單射(或雙射)；θ：Y→[k+8m+1，q+8m]-{k+14m}是單射。

因而，映射θ：V(2C4m∪Gk+6m)→[0，q+8m]-{k+2m}是單射。

θ′：E(Gk+6m)→[8m+1，q+8m]是雙射。

因而，映射θ′：E(2C4m∪Gk+6m)→[1，q+8m]一一對應，θ就是非連通圖2C4m∪Gk+6m的缺k+2m標號值的優美標號。

定理5 對任意正整數m，如果6m+1≤k+6m+1≤|E(G)|，則非連通圖2C4m∪Gk+6m+1存在缺k+6m標號值的優美標號。

定義非連通圖2C4m∪Gk+6m+1的頂點標號θ為：

θ：X→[0，k]是單射(或雙射)；θ：Y→[k+8m+1，q+8m]-{k+14m+1}是單射；

因而，映射θ：V(2C4m∪Gk+6m+1)→[0，q+8m]-{k+6m}是單射。

θ′：E(Gk+6m+1)→[8m+1，q+8m]是雙射。

因而，映射θ′：E(2C4m∪Gk+6m+1)→[1，q+8m]一一對應，θ就是非連通圖2C4m∪Gk+6m+1的缺k+6m標號值的優美標號。

引理1[3]圈c4n存在特征為2n-1，且缺3n的交錯標號。

注意到：3n=(2n-1)+n+1，由定理1和引理1有以下推論。

推論1 對任意正整數m，非連通圖2C4m∪C8m-4存在特征為8m-3且缺12m-3標號值的交錯標號。

例1 當m=2時，非連通圖2C8∪C12的特征為13且缺21標號值的交錯標號為：

20，6，19，7，18，9，25，10；

17，11，16，8，15，12，14，13；

0，28，1，27，2，26，3，24，4，23，5，22。

注意到：12m-3=(8m-3)+4m，由定理和推論1有如下推論。

推論2 對任意正整數m，非連通圖2C8m∪(2C4m∪C8m-4)存在特征為16m-3且缺24m-3標號值的交錯標號。

例2 當m=4時，非連通圖2C16∪(2C8∪C12)的特征為29且缺45標號值的交錯標號為：

37，23，36，24，35，25，34，18，33，26，32，27，31，28，30，29；

44，14，43，15，42，16，41，17，40，19，39，20，38，21，53，22；

52，6，51，7，50，9，57，10；

49，11，48，8，47，12，46，13；

0，60，1，59，2，58，3，56，4，55，5，54。

注意到：24m-3=(16m-3)+8m，由定理1和推論2有如下推論。

推論3 對任意正整數m，非連通圖2C16m∪(2C8m∪(2C4m∪C8m-4))存在特征為32m-3且缺48m-3標號值的交錯標號。

注意到：48m-3=(32m-3)+16m，由定理1和推論3有如下推論。

推論4 對任意正整數m，非連通圖2C32m∪(2C16m∪(2C8m∪(2C4m∪C8m-4)))存在特征為64m-3且缺96m-3標號值的交錯標號。

重復上述過程，可以構造出許多交錯圖。

注意到：3n=(2n-1)+n+1，由定理2和引理1有如下推論。

推論5 對任意正整數m，非連通圖2C4m∪C24m-8存在缺20m-5標號值的優美標號。

例3 當m=2時，非連通圖2C8∪C40缺35標號值的優美標號為：

23，29，24，32，25，28，26，27；

20，34，21，33，22，31，46，30

0，56，1，55，2，54，3，53，4，52，5，51，6，50，7，49，8，48，9，47，10，45，11，44，12，43，13，42，14，41，15，40，16，39，17，38，18，37，19，36。

注意到：3n=(2n-1)+n+1，由定理3和引理1有如下推論。

推論6 對任意正整數m，非連通圖2C4m∪C24m-4存在缺12m-2標號值的優美標號。

例4 當m=2時，非連通圖2C8∪C44缺22標號值的優美標號為：

26，32，27，35，28，31，29，30；

23，37，24，36，25，34，49，33

0，60，1，59，2，58，3，57，4，56，5，55，6，54，7，53，8，52，9，51，10，50，11，48，12，47，13，46，14，45，15，44，16，43，17，42，18，41，19，40，20，39，21，38。

注意到：3n=(2n-1)+n+1，由定理4和引理1有如下推論。

推論7 對任意正整數m，非連通圖2C4m∪C24m-4存在缺14m-3標號值的優美標號。

例5 當m=2時，非連通圖2C8∪C44缺25標號值的優美標號為：

37，22，36，23，34，24，33，49；

26，32，27，35，28，31，29，30；

0，60，1，59，2，58，3，57，4，56，5，55，6，54，7，53，8，52，9，51，10，50，11，48，12，47，13，46，14，45，15，44，16，43，17，42，18，41，19，40，20，39，21，38。

注意到：3n=(2n-1)+n+1，由定理5和引理1有如下推論。

推論8 對任意正整數m，非連通圖2C4m∪C24m存在缺18m-1標號值的優美標號。

例6 當m=2時，非連通圖2C8∪C48缺35標號值的優美標號為：

39，24，38，26，37，27，36，52；

34，28，33，25，32，29，31，30；

0，64，1，63，2，62，3，61，4，60，5，59，6，58，7，57，8，56，9，55，10，54，11，53，12，51，13，50，14，49，15，48，16，47，17，46，18，45，19，44，20，43，21，42，22，41，23，40。

[1] 馬克杰.優美圖[M].北京：北京大學出版社，1991.

[2] 董俊超.C4k∪C4k∪Cm的優美性[J].煙臺大學學報：自然科學與工程版，1999，12(4)：238-241.

[3] 吳躍生，王廣富，徐保根.非連通圖2C4m∪G的優美標號[J].煙臺大學學報：自然科學與工程版，2014，27(4)：240-243.

(責任編校：夏玉玲)

On Five Sufficient Conditions for the Gracefulness of Unconnected Graph 2C4m∪G

WU Yue-sheng

(School of Science， East China Jiaotong University， Nanchang 330013，China )

The author of this paper discusses the gracefulness of the unconnected graph 2C4m∪Gand puts forward five sufficient conditions for the gracefulness of the unconnected graph.

graceful graph；alternative graph； unconnected graph； graceful labeling

O157.5

A

1672-349X(2015)03-0004-04

10.16160/j.cnki.tsxyxb.2015.03.002