三探非連通圖C4m-1∪G的優(yōu)美標(biāo)號

吳躍生

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

?

三探非連通圖C4m-1∪G的優(yōu)美標(biāo)號

吳躍生

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

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

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

1 相關(guān)定義

圖的優(yōu)美標(biāo)號問題是組合數(shù)學(xué)中一個(gè)熱門課題[1-18].

文中所討論的圖均為無向簡單圖，V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集，記號[m，n]表示整數(shù)集合{m，m+1，…，n}，其中m和n均為非負(fù)整數(shù)，且滿足0≤m

定義1[2]對于一個(gè)圖G=(V，E)，若存在一個(gè)單射θ:V(G)→[0，|E(G)|]使得對所有邊e=uv∈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)值.

與圈有關(guān)的圖的優(yōu)美性是人們研究的一個(gè)重點(diǎn).Rosa A[1]已經(jīng)證明:圈C4n和圈C4n+3都是優(yōu)美的.將由m個(gè)互不相交的n回路Cn所組成的圖記作mCn.Anton Kotzig猜想[2]:對每一對自然數(shù)j和k，jC4k是優(yōu)美圖.這個(gè)猜想沒有得到證明或否定.有許多論文討論了若干圈的非連通并圖的優(yōu)美性.

文獻(xiàn)[13]討論了非連通圖C4m-1∪G的優(yōu)美性，給出了非連通圖C4m-1∪G是優(yōu)美圖的2個(gè)充分條件：對任意正整數(shù)m，若圖G是特征為k且缺k+3m-1標(biāo)號值的交錯(cuò)圖(3m-1≤k+3m-1≤|E(G)|)，則非連通圖C4m-1∪G存在缺標(biāo)號值k+1的優(yōu)美標(biāo)號；對任意正整數(shù)m，若圖G是特征為k且缺k+m+1標(biāo)號值的交錯(cuò)圖(m+1≤k+m+1≤|E(G)|)，則非連通圖C4m-1∪G存在缺標(biāo)號值k+1的優(yōu)美標(biāo)號.證明了:對任意正整數(shù)m，非連通圖C4m-1∪C4m存在缺標(biāo)號值2m的優(yōu)美標(biāo)號;對任意正整數(shù)m，非連通圖C4m-1∪C12m-8存在缺標(biāo)號值6m-4的優(yōu)美標(biāo)號.

文獻(xiàn)[17]再討論了非連通圖C4m-1∪G的優(yōu)美性，給出了非連通圖C4m-1∪G是優(yōu)美圖的2個(gè)充分條件：對任意正整數(shù)m，若圖G是特征為k且缺k+3m-2標(biāo)號值的交錯(cuò)圖(3m-2≤k+3m-2≤|E(G)|)，則非連通圖C4m-1∪G存在缺標(biāo)號值k+4m-1的優(yōu)美標(biāo)號；對任意正整數(shù)m，若圖G是特征為k且缺k+m標(biāo)號值的交錯(cuò)圖(m≤k+m≤|E(G)|)，則非連通圖C4m-1∪G存在缺標(biāo)號值k+4m-1的優(yōu)美標(biāo)號.證明了:對任意正整數(shù)m，非連通圖C4m-1∪C12m-12存在缺標(biāo)號值10m-8的優(yōu)美標(biāo)號；對任意正整數(shù)m，非連通圖C4m-1∪C4m-4存在缺標(biāo)號值6m-4的優(yōu)美標(biāo)號.

筆者繼續(xù)討論非連通圖C4m-1∪G的優(yōu)美性，再給出非連通圖C4m-1∪G是優(yōu)美圖的2個(gè)充分條件.將證明:對任意正整數(shù)m，非連通圖C4m-1∪C8m-4存在缺標(biāo)號值4m-3的優(yōu)美標(biāo)號;對任意正整數(shù)m(m≥2)，非連通圖C4m-1∪C8m-8存在缺標(biāo)號值7m-6的優(yōu)美標(biāo)號.

定義2[2]設(shè)f為G的一個(gè)優(yōu)美標(biāo)號，若存在一個(gè)正整數(shù)k，使得對?uv∈E(G)有f(u)>k≥f(v)或f(u)≤k

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

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

定理1對任意正整數(shù)m，若圖G是特征為k且缺k+2m標(biāo)號值的交錯(cuò)圖(2m≤k+2m≤|E(G)|)，則非連通圖C4m-1∪G存在缺標(biāo)號值k+m的優(yōu)美標(biāo)號.

定義C4m-1∪G的頂點(diǎn)標(biāo)號θ為：

下面證明θ是非連通圖C4m-1∪G的優(yōu)美標(biāo)號.

(ⅰ)θ:X→[0，k]是單射(或雙射)；θ:Y→[k+4m，q+4m-1]-{6m-1+k}是單射;θ:V(C4m-1)→[k+1，k+4m-1]∪{6m-1+k}-{k+m}是單射;θ:V(C4m-1∪G)→[0，q+4m-1]-{k+m}是單射.

(ⅱ)θ′:E(C4m-1)→[1，4m-1]是雙射；θ′：E(G)→[4m，q+4m-1]是雙射.θ′：E(C4m-1∪G)→[1，q+4m-1]是一一對應(yīng).

由(ⅰ)和(ⅱ)可知，θ就是非連通圖C4m-1∪G的缺k+m標(biāo)號值的優(yōu)美標(biāo)號.證畢.

定理2對任意正整數(shù)m(m≥2)，若圖G是特征為k且缺k+2m-1標(biāo)號值的交錯(cuò)圖(2m-1≤k+2m-1≤|E(G)|)，則非連通圖C4m-1∪G存在缺標(biāo)號值k+3m-1的優(yōu)美標(biāo)號.

定義C4m-1∪G的頂點(diǎn)標(biāo)號θ為：

下面證明θ是非連通圖C4m-1∪G的優(yōu)美標(biāo)號.

(ⅰ)θ:X→[0，k]是單射(或雙射);θ:Y→[k+4m，q+4m-1]-{6m-1+k}是單射;θ:V(C4m-1)→[k+1，k+4m-1]∪{6m-2+k}-{k+3m-1}是單射;θ:V(C4m-1∪G)→[0，q+4m-1]-{k+3m-1}是單射.

(ⅱ)θ′:E(C4m-1)→[1，4m-1]是雙射；θ′：E(G)→[4m，q+4m-1]是雙射.θ′：E(C4m-1∪G)→[1，q+4m-1]是一一對應(yīng).

由(ⅰ)和(ⅱ)可知，θ就是非連通圖C4m-1∪G的缺k+3m-1標(biāo)號值的優(yōu)美標(biāo)號.證畢.

定義4[5-8]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.

引理1[5]對任意正整數(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，由定理1和引理1有以下結(jié)論：

推論1對任意正整數(shù)m，n，任意自然數(shù)r，當(dāng)2m-1=n(r+1)時(shí)，非連通圖C4m-1∪C4n(r，r，…，r)存在缺標(biāo)號值5m-3的優(yōu)美標(biāo)號.特別地，當(dāng)r=0時(shí)，對任意正整數(shù)m，非連通圖C4m-1∪C8m-4存在缺標(biāo)號值5m-3的優(yōu)美標(biāo)號.

例1由推論1給出的當(dāng)m=4，n=7，r=0時(shí)，非連通圖C15∪C28存在缺標(biāo)號值17的優(yōu)美標(biāo)號為:

28，14，27，15，26，16，25，18，24，19，23，20，22，21，36;

0，43，1，42，2，41，3，40，4，39，5，38，6，37，7，35，8，34，9，33，10，32，11，31，12，30，13，29.

由推論1給出的當(dāng)m=4，n=1，r=6時(shí)，非連通圖C15∪C4(6，6，6，6)存在缺標(biāo)號值17的優(yōu)美標(biāo)號為:

28，14，27，15，26，16，25，18，24，19，23，20，22，21，36;

0(43，42，41，40，39，38)，37(1，2，3，4，5，6)，7(35，34，33，32，31，30)，29(8，9，10，11，12，13).

注意到3m(r+1)=(2m(r+1)-1)+m(r+1)+1，由定理2和引理1有以下結(jié)論：

推論2對任意正整數(shù)m，n，任意自然數(shù)r，當(dāng)2m-2=n(r+1)時(shí)，非連通圖C4m-1∪C4n(r，r，…，r)存在缺標(biāo)號值7m-6的優(yōu)美標(biāo)號.特別地，當(dāng)r=0時(shí)，對任意正整數(shù)m，非連通圖C4m-1∪C8m-8存在缺標(biāo)號值7m-6的優(yōu)美標(biāo)號.

例2由推論2給出的當(dāng)m=5，n=8，r=0時(shí)，非連通圖C19∪C32存在缺標(biāo)號值29的優(yōu)美標(biāo)號為:

34，16，33，17，32，18，31，19，30，20，28，21，27，22，26，23，25，24，43;

0，51，1，50，2，49，3，48，4，47，5，46，6，45，7，44，8，42，9，41，10，40，11，39，12，38，13，37，14，36，15，35.

由推論2給出的當(dāng)m=4，n=4，r=1時(shí)，非連通圖C19∪C16(1，1，…，1)存在缺標(biāo)號值29的優(yōu)美標(biāo)號為:

34，16，33，17，32，18，31，19，30，20，28，21，27，22，26，23，25，24，43;

0(51)，50(1)，2(49)，48(3)，4(47)，46(5)，6(45)，44(7)，8(42)，41(9)，10(40)，39(11)，12(38)，37(13)，14(36)，35(15).

由推論2給出的當(dāng)m=4，n=2，r=3時(shí)，非連通圖C19∪C8(3，3，…，3)存在缺標(biāo)號值29的優(yōu)美標(biāo)號為:

34，16，33，17，32，18，31，19，30，20，28，21，27，22，26，23，25，24，43;

0(51，50，49)，48(1，2，3)，4(47，46，45)，44(5，6，7)，8(42，41，40)，39(9，10，11)，12(38，37，36)，35(13，14，

15).

由推論2給出的當(dāng)m=4，n=1，r=7時(shí)，非連通圖C19∪C8(3，3，…，3)存在缺標(biāo)號值29的優(yōu)美標(biāo)號為:

34，16，33，17，32，18，31，19，30，20，28，21，27，22，26，23，25，24，43;

0(51，50，49，48，47，46，45)，44(1，2，3，4，5，6，7)，8(42，41，40，39，38，37，36)，35(9，10，11，12，13，14，15).

由C4m-1是優(yōu)美圖和引理2有以下結(jié)論：

由推論1和引理2有以下結(jié)論：

由推論2和引理2有以下結(jié)論：

由文獻(xiàn)[13]可知，C4m-1∪C4m是優(yōu)美圖.再由引理2有以下結(jié)論：

由文獻(xiàn)[13]可知，C4m-1∪C12m-8是優(yōu)美圖.再由引理2有以下結(jié)論：

由文獻(xiàn)[17]可知，C4m-1∪C12m-12是優(yōu)美圖.再由引理2有以下結(jié)論：

由文獻(xiàn)[17]可知，C4m-1∪C4m-4是優(yōu)美圖.再由引理2有以下結(jié)論：

[1] ROSE A.On Certain Valuations of the Vertices of a Graph[M]∥ROSENTHIEHL P，Ed..Theory of Graphs (Internat. Sympos.，Rome，1966).New York and Dunod Paris:Gordon and Breach，1967:349-355.

[2] 馬克杰.優(yōu)美圖[M].北京:北京大學(xué)出版社，1991.

[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] 吳躍生.圖C7(r1，r2，r3，r4，r5，0，0)∪St(m)的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版，2012，33(5):1-9.

[7] 吳躍生，徐保根.兩類非連通圖(P2∨K的優(yōu)美性[J].中山大學(xué)學(xué)報(bào):自然科學(xué)版，2012，51(5):63-66.

[8] 吳躍生.關(guān)于圖P36k+5∪P3n的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版，2012，33(3):4-7.

[9] 吳躍生，王廣富，徐保根.關(guān)于C4h+1⊙K1的(Gr1，Gr2，…，Gr4h+1，Gr4h+2)-冠的優(yōu)美性[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，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] JOSEPH A GALLIAN.A Dynamic Survey of Graph Labeling[J].The Electronic Journal of Combinatorics，2013，16(DS6):1-308.

[13] 吳躍生.非連通圖C4m-1∪G的優(yōu)美標(biāo)號[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版，2014，35(3):1-3.

[14] 吳躍生.非連通圖D2，8∪G的優(yōu)美性[J].西華師范大學(xué)學(xué)報(bào):自然科學(xué)版，2014:35(1):4-6.

[15] 吳躍生.非連通圖G+e∪Hk-1的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版，2014，35(2):3-5.

[16] 賈慧羨，左大偉.與扇圖相關(guān)的2類圖的超邊優(yōu)美標(biāo)號[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版，2014，35(2):6-9.

[17] 吳躍生.再探非連通圖C4m-1∪G的優(yōu)美標(biāo)號[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版，2015，36(1):1-4.

[18] 吳躍生.非連通圖Gn-1∪ki=0C3i(2n+1)的優(yōu)美性[J].河南教育學(xué)院學(xué)報(bào)，2013，22(4):7-9.

(責(zé)任編輯 向陽潔)

Further Exploration of the Graceful Labeling of the Unconnected GraphC4m-1∪G

WU Yuesheng

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

The gracefulness of the unconnected graphC4m-1∪Gis discussed.Two sufficient conditions are given for the gracefulness of unconnected graphC4m-1∪G.

graceful graph;alternating graph;unconnected graph;graceful labeling

1007-2985(2015)04-0005-04

吳躍生(1959—)，男，江西瑞金人，華東交通大學(xué)理學(xué)院副教授，碩士，主要從事圖論研究.

O157.5

A

10.3969/j.issn.1007-2985.2015.04.002