吳 躍 生

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

1 主要概念

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

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

本文討論非連通圖C4m-1∪C12m-8∪G的優(yōu)美性.

定義1[1]對于一個圖G=(V,E),如果存在一個單射θ:V(G)→[ 0, |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)值.

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

f(u)>k≥f(v) 或f(u)≤k

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

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

定義3[1]在平衡二分圖G中,設(shè)其優(yōu)美標(biāo)號θ的特征為k,并且θ(u0)=k,θ(v0)=k+1,則稱u0為G的二分點(diǎn),v0為G的對偶二分點(diǎn).

定義5[3-4]V(G)= {u1,u2,…,un}的每個頂點(diǎn)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.

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

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

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

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

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

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

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

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

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

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

(1)θ:X→[0,k]是單射(或雙射);

θ:Y→[k+16m-8,q+16m-9]-{k+22m-12}是單射(或雙射);

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

θ:V(C12m-8)→[k+2,6m-2+k]∪[10m-3+k,16m-9+k]∪{22m-12+k}-{3m+k}是單射(或雙射);

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

θ′(x2m+2x2m+1)=4m-1;

θ′(x2mx2m+1)=4m-2,θ′(x4m-1x1)=2m-2;

θ′:E(C4m-1)→[1,4m-1]是雙射;

θ′(y12m-9y12m-8)=16m-10;

θ′(y12m-10y12m-9)=16m-9,θ′(y12m-8y1)=10m-7;

θ′:E(C12m-8)→[4m,12m-9]是雙射;

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

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

引理1 對于任意正整數(shù)n,設(shè)C4n是有4n個頂點(diǎn)的圈,則C4n存在特征為2n-1且缺3n的交錯標(biāo)號.

證明 記圈C4n上的頂點(diǎn)依次為v1,v2,…,v4n,定義圈C4n的頂點(diǎn)標(biāo)號θ為

容易驗(yàn)證,θ就是圈C4n的特征為2n-1且缺3n的交錯標(biāo)號.

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

推論1 對于任意正整數(shù)m,非連通圖C4m-1∪C12m-8∪C24m-16存在缺標(biāo)號值12m-8的優(yōu)美標(biāo)號.

例1 由推論1,非連通圖C7∪C16∪C32存在缺標(biāo)號值16的優(yōu)美標(biāo)號為

31,26,30,27,21,28,29,31;

38,17,37,18,36,19,35,20,34,22,33,23,32,24,47,25,38;

0,55,1,54,2,53,3,52,4,51,5,50,6,49,7,48,8,46,9,45,10,44,11,43,12,42,13,41,14,40,15,39,0.

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

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

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

例2 由推論2,非連通圖C7∪C16∪C32(1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,0,…,0)存在缺標(biāo)號值16的優(yōu)美標(biāo)號為

31,26,30,27,21,28,29,31;

38,17,37,18,36,19,35,20,34,22,33,23,32,24,47,25,38;

0(91),90,1(89,88),87,2(86,85,84),83,3(82,81,80,79),78,4(77,76,75,74,73),72,5(71,70,69,68,67,66),65,6(64,63,62,61,60,59,58),57,7(56,55,54,53,52,51,50,49),48,8,46,9,45,10,44,11,43,12,42,13,41,14,40,15,39,0.

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

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

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

例3 由推論3給出的非連通圖C7∪C16∪C16(1,1,…,1)缺標(biāo)號值16的優(yōu)美標(biāo)號為

31,26,30,27,21,28,29,31;

38,17,37,18,36,19,35,20,34,22,33,23,32,24,47,25,38;

0(55),54(1),2(53),52(3),4(51),50(5),6(49),48(7),8(46),45(9),10(44),43(11),12(42),41(13),14(40), 39(15),0(55).

由推論3給出的非連通圖C7∪C16∪C8(3,3,…,3)缺標(biāo)號值16的優(yōu)美標(biāo)號為

31,26,30,27,21,28,29,31;

38,17,37,18,36,19,35,20,34,22,33,23,32,24,47,25,38;

0(55,54,53),52(1,2,3),4(51,50,49),48(5,6,7),8(46,45,44),43(9,10,11),12(42,41,40),39(13,14,15),0(55,54,53).

由推論3給出的非連通圖C7∪C16∪C4(7,7,7,7)缺標(biāo)號值16的優(yōu)美標(biāo)號為

31,26,30,27,21,28,29,31;

38,17,37,18,36,19,35,20,34,22,33,23,32,24,47,25,38;

0(55,54,53,52,51,50,49),48(1,2,3,4,5,6,7),8(46,45,44,43,42,41,40),39(9,10,11,12,13,14,15),0(55,54,53,52,51,50,49).

3 結(jié) 語

本文研究了非連通圖C4m-1∪C12m-8∪G的優(yōu)美標(biāo)號,給出了非連通圖C4m-1∪C12m-8∪G是優(yōu)美圖的一個充分條件,可為繼續(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é)報:理學(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é)報, 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é)報:自然科學(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é)報:自然科學(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é)報:自然科學(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é)報:自然科學(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é)報, 2012,29(6):26-29.

(Wu Yuesheng,Wang Guangfu,Xu Baogen. The Gracefu-lness 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, 2002(5):1-106.