非連通圖2C4m∪G是優(yōu)美圖的5個(gè)充分條件

吳躍生

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

非連通圖2C4m∪G是優(yōu)美圖的5個(gè)充分條件

吳躍生

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

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

優(yōu)美圖；交錯(cuò)圖；非連通圖；優(yōu)美標(biāo)號(hào)

1 相關(guān)概念

圖的優(yōu)美標(biāo)號(hào)問(wèn)題是組合數(shù)學(xué)中的一個(gè)熱門課題。

定義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)。

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

文獻(xiàn)[1]已經(jīng)證明了非連通圖2C4m是優(yōu)美圖。文獻(xiàn)[2]研究了非連通圖2C4m∪Cn的優(yōu)美性，證明了非連通圖2C4m∪C8m-1，2C4(3m-1)∪C8m-1和2C4(3m+1)∪C4(2m+1)是優(yōu)美圖。文獻(xiàn)[3]討論了非連通圖2C4m∪G的優(yōu)美性，給出了非連通圖2C4m∪G是優(yōu)美圖的一個(gè)充分條件：對(duì)任意正整數(shù)m，設(shè)G是特征為k，且缺k+2m+1標(biāo)號(hào)值的交錯(cuò)圖，則非連通圖2C4m∪G存在特征為4m+k+1，且缺k+1標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)(2m+1≤k+2m+1≤|E(G)|)。

本文繼續(xù)討論非連通圖2C4m∪G的優(yōu)美性，給出非連通圖2C4m∪G的是優(yōu)美圖的五個(gè)充分條件。

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

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

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

θ(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]一一對(duì)應(yīng)，所以θ就是非連通圖2C4m∪Gk+2m的缺k+8m標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

所以，θ就是非連通圖2C4m∪Gk+2m的特征為4m+k，且缺k+8m標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。證畢。

定理2 對(duì)任意正整數(shù)m，如果6m-1≤k+6m-1≤|E(G)|，則非連通圖2C4m∪Gk+6m-1存在缺k+8m標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

θ(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。

順應(yīng)論視角下的美劇字幕翻 譯 ………………………………………………………………………… 安 紅（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]一一對(duì)應(yīng)，θ就是非連通圖2C4m∪Gk+6m-1的缺k+8m標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定理3 對(duì)任意正整數(shù)m，如果6m≤k+6m≤|E(G)|，則非連通圖2C4m∪Gk+6m存在缺k+1標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

θ(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]一一對(duì)應(yīng)，θ就是非連通圖2C4m∪Gk+6m的缺k+1標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定理4 對(duì)任意正整數(shù)m，如果6m≤k+6m≤|E(G)|，則非連通圖2C4m∪Gk+6m存在缺k+2m標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

θ：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]一一對(duì)應(yīng)，θ就是非連通圖2C4m∪Gk+6m的缺k+2m標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定理5 對(duì)任意正整數(shù)m，如果6m+1≤k+6m+1≤|E(G)|，則非連通圖2C4m∪Gk+6m+1存在缺k+6m標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

θ：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]一一對(duì)應(yīng)，θ就是非連通圖2C4m∪Gk+6m+1的缺k+6m標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

引理1[3]圈c4n存在特征為2n-1，且缺3n的交錯(cuò)標(biāo)號(hào)。

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

推論1 對(duì)任意正整數(shù)m，非連通圖2C4m∪C8m-4存在特征為8m-3且缺12m-3標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

例1 當(dāng)m=2時(shí)，非連通圖2C8∪C12的特征為13且缺21標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)為：

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

例2 當(dāng)m=4時(shí)，非連通圖2C16∪(2C8∪C12)的特征為29且缺45標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)為：

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 對(duì)任意正整數(shù)m，非連通圖2C16m∪(2C8m∪(2C4m∪C8m-4))存在特征為32m-3且缺48m-3標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

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

推論4 對(duì)任意正整數(shù)m，非連通圖2C32m∪(2C16m∪(2C8m∪(2C4m∪C8m-4)))存在特征為64m-3且缺96m-3標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

重復(fù)上述過(guò)程，可以構(gòu)造出許多交錯(cuò)圖。

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

推論5 對(duì)任意正整數(shù)m，非連通圖2C4m∪C24m-8存在缺20m-5標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

例3 當(dāng)m=2時(shí)，非連通圖2C8∪C40缺35標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

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 對(duì)任意正整數(shù)m，非連通圖2C4m∪C24m-4存在缺12m-2標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

例4 當(dāng)m=2時(shí)，非連通圖2C8∪C44缺22標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

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 對(duì)任意正整數(shù)m，非連通圖2C4m∪C24m-4存在缺14m-3標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

例5 當(dāng)m=2時(shí)，非連通圖2C8∪C44缺25標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

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 對(duì)任意正整數(shù)m，非連通圖2C4m∪C24m存在缺18m-1標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

例6 當(dāng)m=2時(shí)，非連通圖2C8∪C48缺35標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

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

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

[3] 吳躍生，王廣富，徐保根.非連通圖2C4m∪G的優(yōu)美標(biāo)號(hào)[J].煙臺(tái)大學(xué)學(xué)報(bào)：自然科學(xué)與工程版，2014，27(4)：240-243.

(責(zé)任編校：夏玉玲)

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