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

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

吳躍生

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西 南昌 330013)

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

關(guān)鍵詞：優(yōu)美圖;交錯圖；非連通圖;優(yōu)美標(biāo)號

文章編號：1007-2985(2015)01-0001-04

中圖分類號：O157.5文獻標(biāo)志碼：A

DOI:10.3969/j.issn.1007-2985.2015.01.001

收稿日期：*2014-05-27

基金項目：國家自然科學(xué)基金資助項目(11261019,11361024)；江西省自然科學(xué)基金資助項目(20114BAB201010)

作者簡介：吳躍生(1959—)，男，江西瑞金人，華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院副教授，碩士，主要從事圖論研究.

1相關(guān)定義

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

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

定義1對于一個圖G=(V,E)，若存在一個單射θ：V(G)→[,|E(G)|]使得對所有邊e=(u,v)∈E(G)，由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的E(G)→[1,|E(G)|]一個雙射，則稱G是優(yōu)美圖,θ是G的一組優(yōu)美標(biāo)號，稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎo)值.

文獻[12]中討論了非連通圖C4m-1∪G的優(yōu)美性，給出了非連通圖C4m-1∪G是優(yōu)美圖的2個充分條件：對任意正整數(shù)m，若圖G是特征為k且缺k+3m-1標(biāo)號值的交錯圖(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)號值的交錯圖(m+1≤k+m+1≤|E(G)|)，則非連通圖C4m-1∪G存在缺標(biāo)號值k+1的優(yōu)美標(biāo)號.文獻[13]中討論了非連通圖D2,8∪G的優(yōu)美性.

筆者繼續(xù)討論非連通圖C4m-1∪G的優(yōu)美性.

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

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

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

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

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

θ(x2i)=4m-i+k-1,i=1,2,…,2m-1;θ(x2i-1)=i+k,i=1,2,…,m;

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

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

(ⅱ)

θ′(x 2m+2x 2m+1)=4m-1；

θ′(x2mx2m+1)=4m-2；θ′(x4m-1x1)=2m-2.

θ′: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+4m-1標(biāo)號值的優(yōu)美標(biāo)號.證畢.

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

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

θ(x2i)=4m-i+k-1,i=1,2,…,m-1;

θ(x2m)=k+5m-1,θ(x2i)=4m-i+k,i=m+1,m+2,…,2m-1;

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

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

(ⅱ)

θ′(x 2m-1x 2m)=4m-1；

θ′(x2mx2m+1)=4m-2；θ′(x4m-1x1)=2m-1.

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

定義4[4-7]V(G)= {u1,u2,…,un}的每個頂點ui都粘接了ri條懸掛邊(ri為自然數(shù)，i=1,2,…,n)所得到的圖，稱為圖G的(r1,r2,…,rn)-冠，簡記為 G(r1,r2,…,rn).特別地，當(dāng)r1=r2=… =rn=r時，稱為圖G的r-冠.圖G的0-冠就是圖G.

引理1對任意正整數(shù)m，任意自然數(shù)r1,r2,…,rm，C4m(r1,0,r2,0,…,rm,0,…,0)存在特征為2m-1,且缺3m的交錯標(biāo)號.

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

推論1對任意正整數(shù)m(m≥2)，任意自然數(shù)r1,r2,…,r3m-3，非連通圖C4m-1∪C12m-12(r1,0,r2,0,…,r3m-3,0,…,0)存在缺標(biāo)號值10m-8的優(yōu)美標(biāo)號.

例1當(dāng)m=2，r1=r2=r3=0時，由推論1給出的非連通圖C7∪C12存在缺標(biāo)號值12的優(yōu)美標(biāo)號為:

C7:6,11,7,10,16,9,8;

C12:0,19,1,18,2,17,3,15,4,14,5,13.

當(dāng)m=2，r1=1,r2=2,r3=3時，由推論1給出的非連通圖C7∪C12(1,0,2,0,3,0,0,…,0)存在缺標(biāo)號值12的優(yōu)美標(biāo)號為：

C7:6,11,7,10,16,9,8;

C12(1,0,2,0,3,0,0,…,0):0(25),24,1(23,22),21,2(20,19,18),17,3,15,4,14,5,13.

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

推論2對任意正整數(shù)m，任意自然數(shù)r1,r2,…,rm-1,非連通圖C4m-1∪C4m-4(r1,0,r2,0,…,rm-1,0,…,0)存在缺6m-4標(biāo)號值的優(yōu)美標(biāo)號.

例2當(dāng)m=3，r1=r2=0時，由推論2給出的非連通圖C11∪C8的缺標(biāo)號值14的優(yōu)美標(biāo)號為：

C11:4,13,5,12,6,17,7,11,8,10,9;

C8：0,19,1,18,2,16,3,15.

當(dāng)m=3，r1=8,r2=9時，由推論2給出的非連通圖C11∪C8(8,0,9,0,0,0,0,0)的缺標(biāo)號值14的優(yōu)美標(biāo)號為：

C11:4,13,5,12,6,17,7,11,8,10,9;

C8(8,0,9,0,0,0,0,0):0(36,35,34,33,32,31,30,29),28,1(27,26,25,24,23,22,21,20,19),18,2,16,3,15.

引理2[10]對任意自然數(shù)n,當(dāng)n≥2時，C2n+1是有2n+1個頂點的圈，Gn-1是邊數(shù)為n-1的優(yōu)美圖，則非連通圖C2n+1∪Gn-1是優(yōu)美的.

因為E(C4m-1)=4m-1，所以由引理2有以下結(jié)論：

推論3設(shè)m為任意的正整數(shù)，則非連通圖C4m-1∪C2(4m)+1是優(yōu)美的.

因為E(C4m-1∪C12m-12(r1,0,r2,0,…,r3m-3))=16m-13+r1+r2+…+r3m-3，令16m-13+r1+r2+…+r3m-3=a,所以由推論1和引理2有以下結(jié)論：

推論4對任意正整數(shù)m(m≥2)，任意自然數(shù)r1,r2,…,r3m-3，非連通圖C4m-1∪C12m-12(r1,0,r2,0,…,r3m-3,0,…,0)∪C2(a+1)+1是優(yōu)美的.

因為E(C4m-1∪C4m-4(r1,0,r2,0,…,rm-1))=8m-5+r1+r2+…+rm-1，令8m-5+r1+r2+…+rm-1=b,所以由推論2和引理2有以下結(jié)論：

推論5對任意正整數(shù)m(m≥2)和任意自然數(shù)r1,r2,…,rm-1，非連通圖C4m-1∪C4m-4(r1,0,r2,0,…,rm-1,0,…,0)∪C2(b+1)+1是優(yōu)美的.

參考文獻：

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

[2]楊顯文.關(guān)于C4m蛇的優(yōu)美性.工程數(shù)學(xué)學(xué)報，1995,12(4):108-112.

[3]吳躍生.關(guān)于圈C4h的(r1,r2,…,r4h)-冠的優(yōu)美性.華東交通大學(xué)學(xué)報,2011,28(1):77-80.

[4]吳躍生,李詠秋.關(guān)于圈C4h+3的(r1,r2,…,r4h+3)-冠的優(yōu)美性.吉首大學(xué)學(xué)報：自然科學(xué)版,2011,32(6):1-4.

[7]吳躍生.圖C7(r1,r2,r3,r4,r5,0,0)∪St(m)的優(yōu)美性.吉首大學(xué)學(xué)報：自然科學(xué)版,2012,33(5):9-11；25.

[8]吳躍生,王廣富，徐保根.關(guān)于C4h+1⊙K1的(Gr1,Gr2,…,Gr4h+1,Gr4h+2)-冠的優(yōu)美性.山東大學(xué)學(xué)報,2013，48(4)：25-27.

[9]吳躍生.關(guān)于圈C4h+3的(Gr1,Gr2,…,Gr4h+3)-冠的優(yōu)美性.吉首大學(xué)學(xué)報：自然科學(xué)版,2013,34(4)：4-9.

[10] 吳躍生,王廣富，徐保根.非連通圖C2n+1∪Gn-1的優(yōu)美性.華東交通大學(xué)學(xué)報,2012,29(6):26-29.

[11] GALLIAN J A.A Dynamic Survey of Graph Labeling.The Electronic Joumal of Combinatorics，2013,16(DS6)：1-308.

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

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

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

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

Revisiting the Graceful Labeling of the Unconnected GraphC4m-1∪G

WU Yuesheng

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

Abstract:The gracefulness of the unconnected graph C4m-1∪G is discussed.Two sufficient conditions are given for the gracefulness of unconnected graph C4m-1∪G.

Key words:graceful graph;balanced bipartite graph;unconnected graph;graceful labeling

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