吳躍生
(華東交通大學(xué) 理學(xué)院,南昌330013)
本文所討論的圖均為無向簡單圖,V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集,記號[m,n]表示整數(shù)集合{m,m+1,…,n},其中m和n均為非負(fù)整數(shù),且滿足0≤m<n。未說明的符號及術(shù)語均同文獻(xiàn)[1]。
圖的優(yōu)美標(biāo)號問題是組合數(shù)學(xué)中一個熱門課題[1-13]。文獻(xiàn)[2]已經(jīng)證明:非連通圖2C4(3m-1)∪C8m-1是優(yōu)美圖。
本文擬討論非連通圖2C4(3m-1)∪C8m-1∪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為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)。
定義4[3]G是一個優(yōu)美二部圖,其優(yōu)美標(biāo)號為θ,V(G)劃分成兩個集合X,Y,如果則稱θ是G的交錯標(biāo)號,稱G是在交錯標(biāo)號θ下的交錯圖。
定理 對任意正整數(shù)m,如果圖G是特征為k且缺k+12m-3標(biāo)號值的交錯圖(12m-3≤k+12m-3≤|E(G)|),非連通圖2C4(3m-1)∪C8m-1∪G存在缺標(biāo)號值k+1的優(yōu)美標(biāo)號。
證明 把2C4(3m-1)中 的 一 個 圈 記 作另 一 個 記設(shè)X,Y是圖G的一個二分化,θ1是圖G的交錯標(biāo)號,且
定義2C4(3m-1)∪C8m-1∪G的頂點(diǎn)標(biāo)號θ為:
下面證 明θ是 非 連 通 圖 2C4(3m-1)∪C8m-1∪G的 優(yōu) 美標(biāo)號。
(1)θ:X→[0,k]是單射(或雙射);θ:Y→[k+32m-8,q+32m-9]-{44m+k-12}是單射(或雙射);
θ:→[k+2,6m+k-1]∪[26m+k-7,32m+k-9]-{29m+k-8}是單射(或雙射);
θ:V()→[6m+k+1,12m+k-2]∪[20m+k-3,26m+k-8]-{29m+k-8,44m+k-12}是單射(或雙射);
θ:V(C)→[12m+k-1,20m+k-4]∪{6m+k}是單射(或雙射);
θ:V(2C4(3m-1)∪C8m-1∪G)→[0,q+32m-9]-{k+1}是單射。
(2)θ′:E()→[20m-6,32m-11]是雙射;
θ′:E()→[8m,20m-7]∪{32m-10,32m-9}是雙射;
θ′:E(C8m-1)→[1,8m-1]是雙射;
θ′:E(G)→[32m-8,q+32m-9]是雙射;
θ′:E(2C4(3m-1)∪C8m-1∪G)→ [1,q+32m-9]是 一 一對應(yīng)。
由(1)和(2)可知θ就是非連通圖2C4(3m-1)∪C8m-1∪G的缺k+1標(biāo)號值的優(yōu)美標(biāo)號。
引理 對任意正整數(shù)n,設(shè)C4n是有4n個頂點(diǎn)的圈,則C4n存在特征為2n-1,且缺3n的交錯標(biāo)號。
證明 記圈C4n上的頂點(diǎn)依次為v1,v2,…,v4n,定義圈C4n的頂點(diǎn)標(biāo)號θ為:
容易驗證,θ就是圈C4n的特征為2n-1,且缺3n的交錯標(biāo)號。
注意到:3n=(2n-1)+n+1,由定理和引理1有以下推論。
推論1 對任意正整數(shù)m,非連通圖2C4(3m-1)∪C8m-1∪C48m-16存在缺標(biāo)號值24m-8的優(yōu)美標(biāo)號。
例1 由推論1,非連通圖2C8∪C7∪C32存在缺標(biāo)號值16的優(yōu)美標(biāo)號為:
38,17 ,37,18,35,19,34,20;
33,22 ,32,23,36,24,47,25;
26,31 ,27,21,28,30,29;
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.
定義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[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有下面的推論。
推論2 對任意正整數(shù)m,任意自然數(shù)r1,r2,…,r12m-4,非連通圖2C4(3m-1)∪C8m-1∪C48m-16(r1,0,r2,0,…,r12m-4,0,0,…,0)存在缺標(biāo)號值24m-8的優(yōu)美標(biāo)號。
例2 由推論2,非連通圖2C8∪C7∪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)號為:
38,17 ,37,18,35,19,34,20;
33,22 ,32,23,36,24,47,25;
26,31 ,27,21,28,30,29;
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.
引理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有下面的推論。
推論3 對任意正整數(shù)m,n,任意自然數(shù)r,當(dāng)12m-4=n(r+1)時,非連通圖2C4(3m-1)∪C8m-1∪C4n(r,r,…,r)存在缺2n(r+1)標(biāo)號值的優(yōu)美標(biāo)號。
例3 由推論3給出的非連通圖2C8∪C7∪C16(1,1,…,1)缺16標(biāo)號值的優(yōu)美標(biāo)號為:
38,17 ,37,18,35,19,34,20;
33,22 ,32,23,36,24,47,25;
26,31 ,27,21,28,30,29;
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).
由推論3給出的非連通圖2C8∪C7∪C8(3,3,…,3)缺16標(biāo)號值的優(yōu)美標(biāo)號為:
38,17 ,37,18,35,19,34,20;
33,22 ,32,23,36,24,47,25;
26,31 ,27,21,28,30,29;
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).
由推論3給出的非連通圖2C8∪C7∪C4(7,7,7,7)缺16標(biāo)號值的優(yōu)美標(biāo)號為:
38,17 ,37,18,35,19,34,20;
33,22 ,32,23,36,24,47,25;
26,31 ,27,21,28,30,29;
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).
引理4[1]對任意正整數(shù)m,2C4m存在特征為4m-1,且缺6m的交錯標(biāo)號。
注意到:6m=(4m-1)+2m+1,由定理和引理4有下面的推論。
推論4 對任意正整數(shù)m,n,當(dāng)6m-2=n時,非連通圖2C4(3m-1)∪C8m-1∪2C4n存在缺24m-8標(biāo)號值的優(yōu)美標(biāo)號。
例4 由推論4給出的非連通圖2C8∪C7∪2C16缺16標(biāo)號值的優(yōu)美標(biāo)號為:
38,17 ,37,18,35,19,34,20;
33,22 ,32,23,36,24,47,25;
26,31 ,27,21,28,30,29;
0,55 ,1,54,2,53,3,52,5,51,6,50,7,49,8,48;
46,9 ,45,10,44,11,43.4.42,12,41.13,40,14,39,15.
引理5[13]對任意正整數(shù)m(m≠3),mC4存在特征為2m-1,且缺3m的交錯標(biāo)號。
注意到:3m=(2m-1)+m+1,由定理和引理5有下面的推論。
推論5 對任意正整數(shù)m,n,當(dāng)12m-1=n時,非連通圖2C4(3m-1)∪C8m-1∪nC4存 在 缺 24m-8 標(biāo) 號 值 的 優(yōu) 美標(biāo)號。
例5 由推論5給出的非連通圖2C8∪C7∪8C4缺16標(biāo)號值的優(yōu)美標(biāo)號為:
38,17 ,37,18,35,19,34,20;
33,22 ,32,23,36,24,47,25;
26,31 ,27,21,28,30,29;
55,0 ,53,1;54,3,48,5;52,2,50,6;51,4,43,11;
49,7 ,45,8;46,10,40,12;44,9,42,13;41,14,39,15.
[1]馬克杰.優(yōu)美圖[M].北京:北京大學(xué)出版社,1991:1-247.
[2]董俊超.C4k∪C4k∪Cm的優(yōu)美性[J].煙臺大學(xué)學(xué)報:自然科學(xué)與工程版,1999,12(4):238-241.
[3]楊顯文.關(guān)于C4m蛇的優(yōu)美性[J].工程數(shù)學(xué)學(xué)報,1995,12(4):108-112.
[4]吳躍生.關(guān)于圈C4h的(r1,r2,…,r4h)-冠的優(yōu)美性[J].華東交通大學(xué)學(xué)報,2011,28(1):77-80.
[5]吳躍生,李詠秋.關(guān)于圈C4h+3的(r1,r2,…,r4h+3)-冠的優(yōu)美性[J].吉首大學(xué)學(xué)報:自然科學(xué)版,2011,32(6):1-4.
[6]吳躍生.關(guān)于圖P6k+53∪Pn3的優(yōu)美性[J].吉首大學(xué)學(xué)報:自然科學(xué)版,2012,33(3):4-7.
[7]吳躍生,徐保根.兩類非連通圖(P2∨珡Kn)(0,0,r1,0,…,0,rn)∪St(m)及(P2∨珡Kn)(r1+a,r2,0,…,0)∪Gr的優(yōu)美性[J].中山大學(xué)學(xué)報:自然科學(xué)版,2012,51(5):63-66.
[8]吳躍生.圖C7(r1,r2,r3,r4,r5,0,0)∪St(m)的優(yōu)美性[J].吉首大學(xué)學(xué)報:自然科學(xué)版,2012,33(5):9-11.
[9]吳躍生,王廣富,徐保根.關(guān)于C4h+1⊙K1的(Gr1,Gr2,…,Gr4h+1,Gr4h+2)-冠 的 優(yōu) 美 性 [J].山 東 大 學(xué) 學(xué) 報,2013,48(4):25-27.
[10]吳躍生.關(guān)于圈C4h+3的(Gr1,Gr2,…,Gr4h+3)-冠的優(yōu)美性[J].吉首大學(xué)學(xué)報:自然科學(xué)版,2013,34(4):4-9.
[11]吳躍生,王廣富,徐保根.非連通圖C2n+1∪Gn-1的優(yōu)美性[J].華東交通大學(xué)學(xué)報,2012,29(6):26-29.
[12]Gallian J A.A dynamic survey of graph labeling[J].The Electronic Joumal of Combinatorics,2012,19,DS6:1-260.
[13]Jaromir Abrham,Anton Kotzig.All 2-regular graphs consisting of 4-cycles are graceful[J].Discrete Mathematics,1994,135(1-3):1-14.