2類優(yōu)美圖的冠的優(yōu)美性證明*

唐保祥,任 韓

(1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院,甘肅 天水 741001;2.華東師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,上海 200062)

圖的優(yōu)美標(biāo)號的研究成果已經(jīng)應(yīng)用于物流運輸、晶體結(jié)構(gòu)中原子位置的測定、X-射線密碼技術(shù)、天文學(xué)、導(dǎo)彈控制、雷達、通訊網(wǎng)絡(luò)尋址、數(shù)據(jù)庫管理等方面[1-3].然而,至今還沒有優(yōu)美圖的系統(tǒng)化研究方法,表征優(yōu)美圖的特征仍然是一個世界難題.目前,對優(yōu)美圖的證明是用構(gòu)造性的方法給出一些特殊圖類的優(yōu)美標(biāo)號,然后證明這些圖是優(yōu)美圖[4-14].馬克杰[1]曾給出一個猜想:任意優(yōu)美圖的冠是優(yōu)美圖.但這一猜想至今未被證明或否定.筆者擬證明優(yōu)美圖Tn和1-∧C4,n的冠I(Tn)和I(1-∧C4,n)都是優(yōu)美圖.

1 相關(guān)概念

定義1[1]設(shè)圖G=(V,E),若存在單射θ:V(G)→{0,1,2,…,|E(G)|},使得?e=uv∈E(G),由θ′(e)=|θ(u)-θ(v)|導(dǎo)出雙射θ′:E(G)→{1,2,…,|E(G)|},則稱圖G是優(yōu)美圖, 稱θ為圖G的一個優(yōu)美標(biāo)號,稱θ′為由θ導(dǎo)出的邊標(biāo)號.

定義2[1]圖G的每個頂點上都粘接r條懸掛邊(r≥1)得到的圖,稱為G的r-冠.G的1-冠稱為G的冠,記作I(G).

將4圈ui1ui2ui3ui4ui1與ui+1,1ui+1,2ui+1,3ui+1,4ui+1,1的頂點ui2與ui+1,1(i=1,2,…,n-1)之間連接一條邊，得到的圖記作∧C4,n,如圖1所示.

圖1 圖∧C4,n

將圖∧C4,n的每個4圈的頂點ui1與ui3之間連接一條長為2的路ui1viui3(i=1,2,…,n)，得到的圖記作1-∧C4,n,如圖2所示.

圖2 圖1-∧C4,n

2條長為n的路為P1=u0u1…un,P2=v0v1…vn,分別連接路P1與P2的頂點ui與vi(i=0,1,…,n)，得到的圖稱為長為n的梯子,記作Tn,如圖3所示.

圖3 圖Tn

為了研究方便,將梯子圖畫成與它同構(gòu)的圖，如圖4所示.

圖4 圖Tn同構(gòu)

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

定理1對于?n∈Z+,圖1-∧C4,n和它的冠I(1-∧C4,n)都是優(yōu)美圖.

證明首先證明圖1-∧C4,n是優(yōu)美圖.設(shè)圖1-∧C4,n的頂點的集合為{ui1,ui2,ui3,ui4,vi|i=1,2,…,n},由圖1-∧C4,n的定義易知,|E(1-C4,n)|=7n-1,|V(1-C4,n)|=5n.定義圖1-∧C4,n的頂點的標(biāo)號θ為

θ(ui4)=3(i-1),θ(vi)=3(i-1)+1,θ(ui2)=3(i-1)+2,

θ(ui1)=7n-1-4(i-1),θ(ui3)=7n-4-4(i-1)i=1,2,…,n.

例如,圖1-∧C4,5的優(yōu)美標(biāo)號如圖5所示.

圖5 圖1-∧C4,5的優(yōu)美標(biāo)號

按照標(biāo)號θ的定義：圖1-∧C4,n的頂點u14,v1,u12,u24,v2,u22,…,un4,vn,un3上的標(biāo)號構(gòu)成等差數(shù)列0,1,2,3,4,5,…,3(n-1),3(n-1)+1,3(n-1)+2,其通項為ai=i-1,i=1,2,…,n；圖1-∧C4,n的頂點u11,u21,u31,…,un1上的標(biāo)號構(gòu)成等差數(shù)列7n-1,7n-5,7n-9,…,7n-1-4(n-1),其通項為bi=7n-1-4(i-1),i=1,2,…,n；圖1-∧C4,n的頂點u13,u23,u33,…,un3上的標(biāo)號構(gòu)成等差數(shù)列7n-4,7n-7,7n-10,…,7n-4-4(n-1),其通項為ci=7n-4-4(i-1),i=1,2,…,n.

因為數(shù)列{ai}的最大項是3n-1,數(shù)列{bi}的最小項是3n+3,數(shù)列{ci}的最小項是3n+4,所以數(shù)列{ai}和{bi}沒有公共項,數(shù)列{ai}和{ci}沒有公共項,而數(shù)列{bi}和數(shù)列{ci}的對應(yīng)項之差為3,從而數(shù)列{bi}和數(shù)列{ci}沒有公共項.因此，映射θ:V(1-∧C4,n)→{0,1,2,…,|E(1-∧C4,n)|}是單射.

因為

{θ(ui1)-θ(ui4),θ(ui1)-θ(vi),θ(ui1)-θ(ui2),θ(ui3)-θ(ui4),θ(ui3)-θ(vi),

θ(ui3)-θ(ui2)}={7n-1-7(i-1),7n-2-7(i-1),7n-3-7(i-1),

7n-4-7(i-1),7n-5-7(i-1),7n-6-7(i-1)}i=1,2,…,n，

{θ(ui+1,1)-θ(ui2)}={7n-7-7(i-1)}i=1,2,…,n-1,

所以圖1-∧C4,n由頂點標(biāo)號導(dǎo)出的邊標(biāo)號的規(guī)律為：從左至右由4圈u11u22u33u44u11及連接該4圈的懸掛邊再到4圈un1un2un3un4un1及連接該4圈的懸掛邊上的邊標(biāo)號分別為7n-1,7n-2,7n-3,…,3,2,1.即由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的映射θ′:E(1-∧C4,n)→{1,2,…,|E(1-∧C4,n)|}是雙射.

于是θ是圖1-∧C4,n的一個優(yōu)美標(biāo)號,圖1-∧C4,n是優(yōu)美圖.

再證明圖1-∧C4,n的冠I(1-∧C4,n)是優(yōu)美圖.設(shè)圖I(1-∧C4,n)的頂點的集合為{ui1,ui2,ui3,ui4,vi,wi,xi1,xi2,yi1,yi2|i=1,2,…,n},如圖6所示.由圖I(1-∧C4,n)的定義易知,|E(I(1-C4,n))|=12n-1,|V(I(1-C4,n))|=10n.定義圖I(1-∧C4,n)的頂點的標(biāo)號θ為

圖6 圖I(1-∧C4,n)

θ(ui4)=6(i-1),θ(vi)=2+6(i-1),θ(ui2)=6(i-1)+4,

θ(xi1)=1+6(i-1),θ(yi2)=5+6(i-1),θ(yi1)=12n-1-6(i-1),

θ(xi2)=12n-4-6(i-1),θ(ui1)=12n-2-6(i-1),

θ(ui3)=12n-5-6(i-1),θ(w1)=12n-9-6(i-1)i=1,2,…,n.

例如,圖I(1-∧C4,5)的優(yōu)美標(biāo)號如圖7所示.

圖7 圖I(1-∧C4,5)的優(yōu)美標(biāo)號

令

S1={θ(xi1)|i=1,2,…,n}={1,7,13,…,1+6(n-1)},

S2={θ(xi2)|i=1,2,…,n}={12n-4,12n-10,12n-16,…,12n-4-6(n-1)},

S3={θ(ui4),θ(vi),θ(ui2)|i=1,2,…,n}={0,2,4,…,4+6(n-1)},

S4={θ(ui1)|i=1,2,…,n}={12n-2,12n-8,12n-14,…,12n-2-6(n-1)},

S5={θ(ui3)|i=1,2,…,n}={12n-5,12n-11,12n-17,…,12n-5-6(n-1)},

S6={θ(wi)|i=1,2,…,n}={12n-9,12n-15,12n-21,…,12n-9-6(n-1)},

S7={θ(yi1)|i=1,2,…,n}={12n-1,12n-7,12n-13,…,12n-1-6(n-1)},

S8={θ(yi2)|i=1,2,…,n}={5,11,17,…,6+6(n-1)}.

因為Sp∩Sq=?(p≠q,p,q∈{1,2,…,8}),所以映射θ:V(I(1-∧C4,n))→{0,1,2,…,|EI((1-∧C4,n))|}是單射.

因為

{θ(yi1)-θ(ui4),θ(ui1)-θ(ui4),θ(ui1)-θ(xi1),θ(ui1)-θ(vi),θ(ui3)-θ(ui4),

θ(ui1)-θ(ui2),θ(ui3)-θ(vi),θ(xi2)-θ(ui2),θ(ui3)-θ(ui2),

θ(ui3)-θ(yi2),θ(wi)-θ(vi)}={12n-1-12(i-1),

12n-2-12(i-1),12n-3-12(i-1),12n-4-12(i-1),

12n-5-12(i-1),12n-6-12(i-1),12n-7-12(i-1),

12n-8-12(i-1),12n-9-12(i-1),

12n-10-12(i-1),12n-11-12(i-1)}i=1,2,…,n,

{θ(ui+1,1)-θ(ui2)}={12n-12-12(i-1)}i=1,2,…,n-1,

所以圖1-∧C4,n的冠I(1-∧C4,5)由頂點標(biāo)號導(dǎo)出的邊標(biāo)號的規(guī)律為：從左至右由4圈u11u22u33u44u11及連接該4圈的懸掛邊再到4圈un1un2un3un4un1及連接該4圈的懸掛邊上的邊標(biāo)號分別為12n-1,12n-2,12n-3,…,3,2,1即由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的映射θ′:EI((1-∧C4,n))→{1,2,…,|EI((1-∧C4,n))|}是雙射.

于是θ是圖I(1-∧C4,n)的一個優(yōu)美標(biāo)號,圖I(1-∧C4,n)是優(yōu)美圖.

定理2對于?n∈Z+,圖Tn和它的冠I(Tn)是優(yōu)美圖.

證明先證圖Tn是優(yōu)美圖.根據(jù)圖Tn的定義,有|V(Tn)|=2n+2,|E(1-Fm,4)|=3n+1.設(shè)V(Tn)={u0,u1,…,un,v0,v1,…,vn},如圖8所示，頂點標(biāo)號顯然是圖Tn的一個優(yōu)美標(biāo)號,所以圖Tn是優(yōu)美圖.

圖8 圖Tn的優(yōu)美標(biāo)號

再證I(Tn)是優(yōu)美圖.設(shè)圖I(Tn)的頂點的集合為{xi,ui,vi,yi|i=1,2,…,n},如圖9所示.由圖I(Tn)的定義易知,|E(I(Tn))|=5n+3,|V(I(Tn))|=4n+4.定義圖I(Tn)的頂點的標(biāo)號θ為

圖9 圖I(Tn)

θ(xi)=1+3i,θ(ui)=5n+2-3i,θ(vi)=2i,θ(yi)=5n+3-3ii=0,1,2,…,n.

例如,圖I(T8)的優(yōu)美標(biāo)號如圖10所示.

圖10 圖I(T8)的優(yōu)美標(biāo)號

令

P1={θ(xi)|i=0,1,2,…,n}={1,3,5,…,1+3n},

P2={θ(ui)|i=0,1,2,…,n}={5n+2,5n-1,5n-4,…,2n+2},

P3={θ(vi)|i=0,1,2,…,n}={0,2,4,…,2n},

P4={θ(yi)|i=0,1,2,…,n}={5n+3,5n,5n-3,…,2n+3},

則Pi∩Pj=?,i≠j,i,j∈{0, 1,2,…,n}.因此,映射θ:V(I(Tn))→{0,1,2,…,4n+3}是單射.

因為

{θ(ui)-θ(xi),θ(ui)-θ(vi),θ(yi)-θ(vi)}={5n+1-5i,

5n+2-5i,5n+3-5i}i=0,1,2,…,n,

所以θ′:E(I(Tn))→{1,2,…,5n+3}是雙射,從而θ是圖I(Tn)的一個優(yōu)美標(biāo)號,圖I(Tn)是優(yōu)美圖.