吳 躍 生

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

?

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

吳 躍 生

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

摘要:討論了非連通圖C4∪C12∪G的優(yōu)美性,證明了當(dāng)m為任意正整數(shù),G是特征為k且缺標(biāo)號(hào)值k+6m-4的交錯(cuò)圖(6m-4≤k+6m-4≤|E(G)|)時(shí),非連通圖C4∪C12∪G存在缺標(biāo)號(hào)值k+16m-9的優(yōu)美標(biāo)號(hào),其中,Cspan是具有m個(gè)頂點(diǎn)的圈.

關(guān)鍵詞:優(yōu)美圖; 平衡二分圖; 非連通圖; 優(yōu)美標(biāo)號(hào)

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

圖的優(yōu)美標(biāo)號(hào)問題是組合數(shù)學(xué)中一個(gè)熱門課題[1-15].文獻(xiàn)[12]討論了非連通圖C4m-1∪G的優(yōu)美性,給出了非連通圖C4m-1∪G是優(yōu)美圖的兩個(gè)充分條件. 文獻(xiàn)[15]討論了非連通圖C4m-1∪C12m-8∪G的優(yōu)美性,給出了非連通圖C4m-1∪C12m-8∪G是優(yōu)美圖的一個(gè)充分條件:對(duì)任意正整數(shù)m(m≥2),如果圖G是特征為k且缺標(biāo)號(hào)值k+6m-3的交錯(cuò)圖(6m-3≤k+6m-3≤|E(G)|),那么非連通圖C4m-1∪C12m-8∪G存在缺標(biāo)號(hào)值k+1的優(yōu)美標(biāo)號(hào).本文繼續(xù)討論了非連通圖C4m-1∪C12m-8∪G的優(yōu)美性,并給出了非連通圖C4m-1∪C12m-8∪G是優(yōu)美圖的幾個(gè)充分條件.

1相關(guān)概念

定義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)|]是一個(gè)雙射,則稱G是優(yōu)美圖, θ是G的一組優(yōu)美標(biāo)號(hào),稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎo)值.

定義2[1]設(shè)f為G的一個(gè)優(yōu)美標(biāo)號(hào),如果存在一個(gè)正整數(shù)k,使得對(duì)任意的uv∈E(G),有

成立,則稱f為G的平衡標(biāo)號(hào)(或稱G有平衡標(biāo)號(hào)f),且稱k為f的特征.圖G稱為平衡二分圖(balanced bipartite graph).

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

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

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

定理1對(duì)任意正整數(shù)m(m≥2),如果圖G是特征為k且缺標(biāo)號(hào)值k+6m-4的交錯(cuò)圖(6m-4≤k+6m-4≤|E(G)|),那么非連通圖C4m-1∪C12m-8∪G存在缺標(biāo)號(hào)值k+16m-9的優(yōu)美標(biāo)號(hào).

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

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

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

θ(x2m+1)=3m+k-1;

θ(x2i-1)=10m-i+k-3

(i=m+2,m+3,…,2m);

θ(y2i-1)=16m-9-i+k(i=1,2,…,6m-5);

θ(y12m-9)=k+22m-13;

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

(1) θ:X→[0, k]是單射; θ:Y→[k+16m-8,q+16m-9]-{k+22m-13}是單射;

θ:V(C4m-1)→[k+6m-2,10m-5+k]∪{3m+k-1}是單射;

θ:V(C12m-8)→[k+1,6m-3+k]∪

[10m-4+k,16m-10+k]∪{22m-13+k}-{3m+k-1}是單射.

因而,映射θ′:E(C4m-1∪C12m-8∪G)→[1, q+16m-9]是一一對(duì)應(yīng)的.

由(1)和(2)可知,θ就是非連通圖C4m-1∪C12m-8∪G的缺標(biāo)號(hào)值k+16m-9的優(yōu)美標(biāo)號(hào).

定理2對(duì)任意正整數(shù)m,如果圖G是特征為k且缺標(biāo)號(hào)值k+2,k+3,…,k+16m-7的交錯(cuò)圖(k+16m-7≤|E(G)|),那么非連通圖C4m-1∪C12m-8∪G存在缺標(biāo)號(hào)值k+1,k+2,…,k+16m-9的優(yōu)美標(biāo)號(hào).

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

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

(1) θ:X→[0, k]是單射; θ:Y→[k+16m-8,q+16m-9]-[k+16m-7,k+32m-16]是單射;

θ:V(G)→[-[k+16m-7,k+32m-16]]是單射.

因而,映射θ: V(C4m-1∪C12m-8∪G)→[0, q+16m-9]-[k+1,k+16m-9]是單射.

(2) θ′:E(C4m-1∪C12m-8)→[1,16m-9]是雙射;

θ′:E(G)→[16m-8,q+16m-9]是雙射.

因而,映射θ′:E(C4m-1∪C12m-8∪G)→[1, q+16m-9]是一一對(duì)應(yīng)的.

由(1)和(2)可知,θ就是非連通圖C4m-1∪C12m-8∪G的缺標(biāo)號(hào)值k+1,k+2,…,k+16m-9的優(yōu)美標(biāo)號(hào).

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

注意到3m=(2m-1)+m+1,由定理1和引理1有如下結(jié)論.

推論1對(duì)任意正整數(shù)m,任意自然數(shù)r1,r2,…,r6m-5,非連通圖C4m-1∪C12m-8∪C24m-20(r1,0,r2,0,…,r6m-5,0,…,0)存在缺標(biāo)號(hào)值28m-20的優(yōu)美標(biāo)號(hào).

例1當(dāng)m=2,ri=0(i=1,2,…,7)時(shí),由推論1,非連通圖C7∪C16∪C28存在缺標(biāo)號(hào)值36的優(yōu)美標(biāo)號(hào)為

C7:28,23,27,24,18,25,26;

C16:35,14,34,15,33,16,32,17,31,19,30,20,29,21,44,22;

C28:0,51,1,50,2,49,3,48,4,47,5,46,6,45,7,43,8,42,9,41,10,40,11,39,12,38,13,37.

當(dāng)m=2,ri=i(i=1,2,…,7)時(shí),由推論1,非連通圖C7∪C16∪C28(1,0,2,0,3,0,4,0,5,0,6,0,7,0,0,…,0)存在缺標(biāo)號(hào)值36的優(yōu)美標(biāo)號(hào)為

C7:28,23,27,24,18,25,26;

C16:35,14,34,15,33,16,32,17,31,19,30,20,29,21,44,22;

C28(1,0,2,0,3,0,4,0,5,0,6,0,7,0,0,…,0):0(79),78,1(77,76),75,2(74,73,72),71,3(70,69,68,67),66,4(65,64,63,62,61),60,5(59,58,57,56,55,54),53,6(52,51,50,49,48,47,46),45,7,43,8,42,9,41,10,40,11,39,12,38,13,37.

引理2[3]對(duì)任意正整數(shù)m,任意自然數(shù)r,C4m(r,r,…,r)存在特征為2m(r+1)-1且缺3m(r+1)的交錯(cuò)標(biāo)號(hào).

注意到3m(r+1)=[2m(r+1)-1]+m(r+1)+1,由定理1和引理2有如下結(jié)論.

推論2對(duì)任意正整數(shù)m,n,任意自然數(shù)r,當(dāng)6m-5=n(r+1)時(shí),非連通圖C4m-1∪C12m-8∪C4n(r,r,…,r)存在缺標(biāo)號(hào)值28m-20的優(yōu)美標(biāo)號(hào).

例2當(dāng)m=2,n=1,r=6時(shí), 由推論2,非連通圖C7∪C16∪C4(6,6,6,6)存在缺標(biāo)號(hào)值36的優(yōu)美標(biāo)號(hào)為

C7:28,23,27,24,18,25,26;

C16:35,14,34,15,33,16,32,17,31,19,30,20,29,21,44,22;

C4(6,6,6,6):0(51,50,49,48,47,46),45(1,2,3,4,5,6),7(43,42,41,40,39,38),37(8,9,10,11,12,13).

引理3[1]對(duì)任意自然數(shù)m,n(m≥2,n≥2),完備二分圖Km,n存在特征為m-1且缺m+1,m+2,…,2m-1的交錯(cuò)標(biāo)號(hào).

注意到m+1=(m-1)+2,m+2=(m-1)+3,…,2m-1=(m-1)+m,由定理1和引理3有如下結(jié)論.

推論3對(duì)任意自然數(shù)h,m,n,當(dāng)h≥2,m≥6h-4,n≥2時(shí),非連通圖C4h-1∪C12h-8∪Km,n存在缺標(biāo)號(hào)值m+16h-10的優(yōu)美標(biāo)號(hào).

例3當(dāng)h=2,m=9,n=3時(shí), 由推論3,非連通圖C7∪C16∪K9,3存在缺標(biāo)號(hào)值31的優(yōu)美標(biāo)號(hào)如圖1所示.

圖1　非連通圖C7∪C16∪K9,3的優(yōu)美標(biāo)號(hào)

由定理2和引理3有如下結(jié)論.

推論4對(duì)任意自然數(shù)h,m,n,當(dāng)h≥1,m≥16h-7,n≥2時(shí),非連通圖C4h-1∪C12h-8∪Km,n存在缺標(biāo)號(hào)值m,m+1,…,m+16h-10的優(yōu)美標(biāo)號(hào).

例4當(dāng)h=1,m=9,n=3時(shí), 由推論4,非連通圖C3∪C4∪K9,3存在缺標(biāo)號(hào)值9,10,…,15的優(yōu)美標(biāo)號(hào)如圖2所示.

圖2　非連通圖(C3∪C4)∪K9,3的第二種優(yōu)美標(biāo)號(hào)

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

由文獻(xiàn)[12]知,C4m-1∪C12m-8是優(yōu)美圖,且|E(C4m-1∪C12m-8)|=16m-9,由引理4有如下結(jié)論.

推論5對(duì)任意正整數(shù)m,非連通圖C4m-1∪C12m-8∪C2(16m-8)+1是優(yōu)美的.

由推論1知, C4m-1∪C12m-8∪C24m-16是優(yōu)美圖,且|E(C4m-1∪C12m-8∪C24m-16)|=40m-25,由引理4有如下結(jié)論.

推論6對(duì)任意正整數(shù)m,非連通圖C4m-1∪C12m-8∪C24m-16∪C2(40m-24)+1是優(yōu)美的.

3結(jié)語

本文研究了非連通圖C4m-1∪C12m-8∪G的優(yōu)美標(biāo)號(hào),給出了非連通圖C4m-1∪C12m-8∪G是優(yōu)美圖的又一個(gè)充分條件,可為繼續(xù)研究非連通圖Cm1∪Cm2∪…∪Cmn∪G的優(yōu)美性提供借鑒.

參考文獻(xiàn):

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

(Ma Kejie. Graceful Graph[M]. Beijing:Beijing University Press, 1991:1-247.)

[ 2 ] 路線,潘偉,李秀芬. 圖St(m)∪Kp,q的k優(yōu)美性及算術(shù)性[J]. 吉林大學(xué)學(xué)報(bào):理學(xué)版, 2004,42(3):333-336.

(Lu Xian, Pan Wei, Li Xiufen.k-Gracefulness and Arithmetic of GraphSt(m) ∪Kp,q[J]. Journal of Jilin University:Science Edition, 2004,42(3):333-336.)

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

(Wu Yuesheng. On the Gracefulness of the (r1,r2,…,r4h)-Corona of the CycleC4h[J]. Journal of East China Jiaotong University, 2011,28(1):77-80.)

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

(Wu Yuesheng ,Li Yongqiu. On the Gracefulness of the (r1,r2,…,r4h+3)-Corona of the CycleC4h+3[J]. Journal of Jishou University:Natural Science Edition, 2011,32(6):1-4.)

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

(Wu Yuesheng. on the Gracefulness of the GraphC7(r1,r2,r3,r4,r5,0,0)∪St(m)[J]. Journal of Jishou University: Natural Science Edition, 2012,33(5):9-11.)

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

(Wu Yuesheng,Wang Guangfu, Xu Baogen. The Gracefulness of the (Gr1,Gr2,…,Gr4h+1,Gr4h+2)-Corona of the GraphC4h+1⊙K1[J]. Journal of Shandong University:Natural Science, 2013,48(4):25-27.)

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

(Wu Yuesheng. On the Gracefulness of the (Gr1,Gr2,…,Gr4h+3)-Corona of the GraphC4h+3[J]. Journal of Jishou University:Natural Science Edition, 2013,34(4):4-9.)

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

(Wu Yuesheng,Wang Guangfu, Xu Baogen. The Gracefulness of the Unconnected GraphC2n+1∪Gn-1[J]. Journal of East China Jiaotong University, 2012,29(6):26-29.)

[11] Gallian J A. A Dynamic Survey of Graph Labeling[J]. The Electronic Journal of Combinatorics, 2009,16:1-308.

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

(Wu Yuesheng. Graceful Labeling of the Unconnected GraphC4m-1∪G[J]. Journal of Jishou University: Natural Science Edition, 2014,35(3):1-3.)

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

(Wu Yuesheng. Gracefulness of the Unconnected GraphG+e∪Hk-1[J]. Journal of Jishou University: Natural Science Edition, 2014,35(2):3-5.)

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

(Jia Huixian, Zuo Dawei. Super-Edge-Graceful Labelings of Two Kinds of Graphs Associated with the Fan Graph[J]. Journal of Jishou University: Natural Science Edition, 2014,35(2):6-9.)

[15] 吳躍生. 非連通圖C4m-1∪C12m-8∪G的優(yōu)美標(biāo)號(hào)[J]. 沈陽大學(xué)學(xué)報(bào):自然科學(xué)版, 2014,26(4):334-337.

【責(zé)任編輯: 王穎】

(Wu Yuesheng. Graceful Labeling of Unconnected GraphC4m-1∪C12m-8∪G[J]. Journal of Shenyang University:Natural Science, 2014,26(4):334-337.)

Further Discussion on Graceful Labeling of Unconnected GraphC4m-1∪C12m-8∪G

WuYuesheng

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

Abstract:The gracefulness of the unconnected graphC4∪C12∪Gis discussed. It is proved that for any positive integerm, whenGis alternating graph (6m-4≤k+6m-4≤|E(G)|) that characterized bykand lack of label values ofk+6m-4, the unconnected graphC4∪C12∪Ghas graceful labeling which lack of lable values ofk+16m-9, wherein,Cspanis a cycle withmvertices.

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

收稿日期:2014-05-24

中圖分類號(hào):O 157.5

文獻(xiàn)標(biāo)志碼:A

作者簡(jiǎn)介:吳躍生(1959-),男,江西瑞金人,華東交通大學(xué)副教授,碩士.

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(11261019,11361024); 江西省教育廳2014年度科學(xué)技術(shù)研究項(xiàng)目(GJJ14380).

文章編號(hào):2095-5456(2015)01-0072-05