童細心

(汕頭職業(yè)技術(shù)學院 自然科學系, 廣東 汕頭 515041)

?

棒棒糖圖的優(yōu)美性

童細心

(汕頭職業(yè)技術(shù)學院 自然科學系, 廣東 汕頭 515041)

摘要:給出了棒棒糖圖Cn+Pl在n=4k,4k-1,4k+1時的優(yōu)美標號，得到了棒棒糖圖Cn+Pl在n=4k,4k-1,4k+1時是優(yōu)美圖的結(jié)論．

關(guān)鍵詞:棒棒糖圖；優(yōu)美標號；優(yōu)美圖．

0引言

優(yōu)美圖是圖論中一個十分有趣且重要的內(nèi)容,它的提出始于1963年G.Ringel[1]的一個猜想,目前其研究成果已經(jīng)被廣泛應用于射電天文學、X-射線衍射晶體學、密碼設(shè)計、通信網(wǎng)絡(luò)編址、導彈控制碼設(shè)計、同步機碼設(shè)計、交通物流控制等領(lǐng)域,至今關(guān)于優(yōu)美圖的研究已得到了很多結(jié)果[1-8].由于缺乏一個系統(tǒng)和有力的工具,迄今,只能對一些特殊圖探索其優(yōu)美性.本文研究了棒棒糖圖Cn+Pl的優(yōu)美性,得到如下結(jié)論:

定理1當n=4k時,棒棒糖圖Cn+Pl是優(yōu)美圖.

定理2當n=4k-1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

定理3當n=4k+1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

定義1[9]對于簡單圖G=(V,E),若?v∈V,存在單射f(v)∈{0,1,2,…,|E|}(f(v)稱為頂點v的標號),且導出的邊標號g(e)=g(uv)=|f(u)-f(v)|是E到{1,2,3,…,|E|}的一個一一對應,則稱圖G是優(yōu)美圖,稱f為圖G的優(yōu)美標號.

圖1　棒棒糖圖Cn+Pn

定義2[10]從圈Cn上的一個頂點ui懸掛一條長為l的路Pl所得到的圖類,稱為棒棒糖圖,記為Cn+Pl.如圖1所示,我們記圈Cn的頂點為ui,i=1,2,…,n.路Pl的頂點為vi,i=1,2,…,l.

本文所討論的圖均為無向簡單圖,v表示頂點v,uv表示以u,v為頂點的邊,f(v)表示點v的標號,簡記為v=f(v);同理,f(uv)表示邊uv的標號,也簡記為uv=f(uv).其他未加說明的定義和符號均來自文[11].

1定理1的證明

1.1情形1當n=4k,l=2t-1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

當n=4k,l=2t-1時,棒棒糖圖Cn+Pl的頂點數(shù)為n+l=4k+2t-1,邊數(shù)為n+l=4k+2t-1.給出棒棒糖圖Cn+Pl的各頂點的標號遞推算法A如下:

(ⅰ)v2i-1=i-1,i=1,2,…,t.

(ⅱ)v2i=4k+2t-i,i=1,2,…,t-1.

(ⅲ)u2i-1=4k+t-i+1,i=1,2,…,2k.

(ⅳ)u2i=t+i-1,i=1,2,…,k;u2i=t+i,i=k+1,k+2,…,2k.

按照算法A可得以下結(jié)果:

引理1當n=4k,l=2t-1時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t-1}構(gòu)成單射.

證明當n=4k,l=2t-1時,記M是棒棒糖圖Cn+Pl的所有頂點標號集合,由算法A的(ⅰ)～(ⅳ)易知:

M1={v2i-1}={i-1|i=1,2,…,t}={0,1,…,t-1};

M2={v2i}={4k+2t-i|i=1,2,…,t-1}={4k+t+1,4k+t+2,…,4k+2t-1};

M3={u2i-1}={4k+t-i+1|i=1,2,…,2k}={2k+t+1,2k+t+2,…,4k+t};

M4={u2i}={t+i-1|i=1,2,…,k}∪{t+i|i=k+1,k+2,…,2k}=

{t,t+1,…,t+k-1}∪{t+k+1,t+k+2,…,t+2k}.

由此易驗證,Mi∩Mj=?,i≠j且i,j=1,2,3,4.即當n=4k,l=2t-1時,棒棒糖圖Cn+Pl中各頂點的標號均不相同.又所有頂點標號的集合M=M1∪M2∪M3∪M4中最小數(shù)是0(在M1中),最大數(shù)是4k+2t-1(在M2中),即當n=4k,l=2t-1時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t-1}構(gòu)成單射.

引理2當n=4k,l=2t-1時,棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t-1}構(gòu)成一一對應.

證明由算法A知,各頂點的標號最小為零,最大為4k+2t-1,故邊的標號均不超過4k+2t-1.我們把邊的標號分為兩大類來考慮.

(Ⅰ)由算法A的(ⅰ)～(ⅲ)可知路v1v2…vlu1中邊的標號有幾種情況:v2i-1v2i=|(4k+2t-i)-(i-1)|=4k+2t-2i+1,其中i=1,2,…,t-1;v2iv2i+1=|(4k+2t-i)-[(i+1)-1]|=4k+2t-2i,其中i=1,2,…,t-1;v2t-1u1=|(4k+t-1+1)-(t-1)|=4k+1.

(Ⅱ)由算法A的(ⅲ)～(ⅳ)可知圈u1u2…u4ku1中邊的標號有幾種情況:u2i-1u2i=|(4k+t-i+1)-(t+i-1)|=4k-2i+2,其中i=1,2,…,k;u2i-1u2i=|(4k+t-i+1)-(t+i)|=4k-2i+1,其中i=k+1,k+2,…,2k;u2iu2i+1=|[4k+t-(i+1)+1]-(t+i-1)|=4k-2i+1,其中i=1,2,…,k;u2iu2i+1=|[4k+t-(i+1)+1]-(t+i)|=4k-2i,其中i=k+1,k+2,…,2k-1;u4ku1=|(4k+t-1+1)-(t+2k)|=2k.

首先,由(Ⅰ)易知,在路v1v2…vlu1中,邊的標號范圍為:4k+3≤v2i-1v2i≤4k+2t-1,其中i=1,2,…,t-1;4k+2≤v2iv2i+1≤4k+2t-2,其中i=1,2,…,t-1;v2t-1u1=4k+1.

由邊的標號范圍及奇偶性知,在路v1v2…vlu1中各邊的標號不相等.

其次,由(Ⅱ)易知,在圈u1u2…u4ku1中,邊的標號范圍為:2k+2≤u2i-1u2i≤4k,其中i=1,2,…,k;1≤u2i-1u2i≤2k-1,其中i=k+1,k+2,…,2k;2k+1≤u2iu2i+1≤4k-1,其中i=1,2,…,k;2≤u2iu2i+1≤2k-2,其中i=k+1,k+2,…,2k-1;u4ku1=2k.

由邊的標號范圍及奇偶性知,在圈u1u2…u4ku1中各邊的標號不相等.

最后,由上易知,兩類邊的標號范圍互不重疊,故也互不相等.

綜上所述,當n=4k,l=2t-1時,棒棒糖圖Cn+Pl各邊的標號均不相同.即當n=4k,l=2t-1時, 棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t-1}構(gòu)成一一對應.

由引理1、引理2及定義1知,情形1成立,即當n=4k,l=2t-1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

1.2情形2當n=4k,l=2t時,棒棒糖圖Cn+Pl是優(yōu)美圖.

當n=4k,l=2t時,棒棒糖圖Cn+Pl的頂點數(shù)為n+l=4k+2t,邊數(shù)為n+l=4k+2t.給出棒棒糖圖Cn+Pl的各頂點的標號遞推算法B如下:

(ⅰ)v2i-1=i-1,i=1,2,…,t.

(ⅱ)v2i=4k+2t-i+1,i=1,2,…,t.

(ⅲ)u2i-1=t+i-1,i=1,2,…,2k.

(ⅳ)u2i=4k+t-i+1,i=1,2,…,k;u2i=4k+t-i,i=k+1,k+2,…,2k.

按照算法B可得以下結(jié)果:

引理3當n=4k,l=2t時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t}構(gòu)成單射.

證明當n=4k,l=2t時,記N是棒棒糖圖Cn+Pl的所有頂點標號集合,由算法B的(ⅰ)～(ⅳ)易知:

N1={v2i-1}={i-1|i=1,2,…,t}={0,1,2,…,t-1};

N2={v2i}={4k+2t-i+1|i=1,2,…,t}={4k+t+1,4k+t+2,…,4k+2t};

N3={u2i-1}={t+i-1|i=1,2,…,2k}={t,t+1,…,t+2k-1};

N4={u2i}={4k+t-i+1|i=1,2,…,k}∪{4k+t-i|i=k+1,k+2,…,2k}=

{3k+t+1,3k+t+2,…,4k+t}∪{2k+t,2k+t+1,…,3k+t-1}.

由此易驗證,Ni∩Nj=?,i≠j且i,j=1,2,3,4.即當n=4k,l=2t時,棒棒糖圖Cn+Pl中各頂點的標號均不相同.又所有頂點標號的集合N=N1∪N2∪N3∪N4中最小數(shù)是0(在N1中),最大數(shù)是4k+2t(在N2中).即當n=4k,l=2t時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t}構(gòu)成單射.

引理4當n=4k,l=2t時,棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t}構(gòu)成一一對應.

證明由算法B知,各頂點的標號最小為零,最大為4k+2t,故邊的標號均不超過4k+2t.我們把邊的標號分為兩大類來考慮.

(Ⅰ)由算法B的(ⅰ)～(ⅲ)可知路v1v2…vlu1中邊的標號有幾種情況:v2i-1v2i=|(4k+2t-i+1)-(i-1)|=4k+2t-2i+2,其中i=1,2,…,t;v2iv2i+1=|(4k+2t-i+1)-[(i+1)-1]|=4k+2t-2i+1,其中i=1,2,…,t-1;v2tu1=|(4k+2t-t+1)-(t+1-1)|=4k+1.

(Ⅱ)由算法B的(ⅲ)～(ⅳ)可知圈u1u2…u4ku1中邊的標號有幾種情況:u2i-1u2i=|(4k+t-i+1)-(t+i-1)|=4k-2i+2,其中i=1,2,…,k;u2i-1u2i=|(4k+t-i)-(t+i-1)|=4k-2i+1,其中i=k+1,k+2,…,2k;u2iu2i+1=|(4k+t-i+1)-[t+(i+1)-1]|=4k-2i+1,其中i=1,2,…,k;u2iu2i+1=|(4k+t-i)-[t+(i+1)-1]|=4k-2i,其中i=k+1,k+2,…,2k-1;u4ku1=|(4k+t-2k)-(t+1-1)|=2k.

首先,由(Ⅰ)易知,在路v1v2…vlu1中,邊的標號范圍為:4k+2≤v2i-1v2i≤4k+2t,其中i=1,2,…,t;4k+3≤v2iv2i+1≤4k+2t-1,其中i=1,2,…,t-1;v2tu1=4k+1.

由邊的標號范圍及奇偶性知,在路v1v2…vlu1中各邊的標號不相等.

其次,由(Ⅱ)易知,在圈u1u2…u4ku1中,邊的標號范圍為:2k+2≤u2i-1u2i≤4k,其中i=1,2,…,k;1≤u2i-1u2i≤2k-1,其中i=k+1,k+2,…,2k;2k+1≤u2iu2i+1≤4k-1,其中i=1,2,…,k;2≤u2iu2i+1≤2k-2,其中i=k+1,k+2,…,2k-1;u4ku1=2k.

由邊的標號范圍及奇偶性知,在圈u1u2…u4ku1中各邊的標號不相等.

最后,由上易知,兩類邊的標號范圍互不重疊,故也互不相等.

綜上所述,當n=4k,l=2t時,棒棒糖圖Cn+Pl各邊的標號均不相同.即當n=4k,l=2t時,棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t}構(gòu)成一一對應.

由引理3、引理4及定義1知,情形2成立,即當n=4k,l=2t時,棒棒糖圖Cn+Pl是優(yōu)美圖.

定理1當n=4k時,棒棒糖圖Cn+Pl是優(yōu)美圖.

證明由情形1、情形2可知,定理1成立.

2定理2的證明

2.1情形3當n=4k-1,l=2t-1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

當n=4k-1,l=2t-1時,棒棒糖圖Cn+Pl的頂點數(shù)為n+l=4k+2t-2,邊數(shù)為n+l=4k+2t-2.此時給出棒棒糖圖Cn+Pl的各頂點的標號遞推算法C如下:

(ⅰ)v2i-1=i-1,i=1,2,…,t.

(ⅱ)v2i=4k+2t-i-1,i=1,2,…,t-1.

(ⅲ)u2i-1=4k+t-i,i=1,2,…,k;u2i-1=4k+t-i-1,i=k+1,k+2,…,2k.

(ⅳ)u2i=t+i-1,i=1,2,…,2k-1.

按照算法C可得以下結(jié)果:

引理5當n=4k-1,l=2t-1時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t-2}構(gòu)成單射.

證明當n=4k-1,l=2t-1時,記P是棒棒糖圖Cn+Pl的所有頂點標號集合,由算法C的(ⅰ)～(ⅳ)易知:

P1={v2i-1}={i-1|i=1,2,…,t}={0,1,…,t-1};

P2={v2i}={4k+2t-i-1|i=1,2,…,t-1}={4k+t,4k+t+1,…,4k+2t-2};

P3={u2i-1}={4k+t-i|i=1,2,…,k}∪{4k+t-i-1|i=k+1,k+2,…,2k}=

{3k+t,3k+t+1,…,4k+t-1}∪{2k+t-1,2k+t,…,3k+t-2};

P4={u2i}={t+i-1|i=1,2,…,2k-1}={t,t+1,…,t+2k-2}.

由此易驗證,Pi∩Pj=?,i≠j且i,j=1,2,3,4.即當n=4k-1,l=2t-1時,棒棒糖圖Cn+Pl中各頂點的標號均不相同.又所有頂點標號的集合P=P1∪P2∪P3∪P4中最小數(shù)是0(在P1中),最大數(shù)是4k+2t-2(在P2中),即當n=4k-1,l=2t-1時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t-2}構(gòu)成單射.

引理6當n=4k-1,l=2t-1時,棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t-2}構(gòu)成一一對應.

證明由算法C知,各頂點的標號最小為零,最大為4k+2t-2,故邊的標號均不超過4k+2t-2.由算法C知,我們把邊的標號分為兩大類來考慮.

(Ⅰ)由算法C的(ⅰ)～(ⅲ)可知路v1v2…vlu1中邊的標號有幾種情況:v2i-1v2i=|(4k+2t-i-1)-(i-1)|=4k+2t-2i,其中i=1,2,…,t-1;v2iv2i+1=|(4k+2t-i-1)-[(i+1)-1]|=4k+2t-2i-1,其中i=1,2,…,t-1;v2t-1u1=|(4k+t-1)-(t-1)|=4k.

(Ⅱ)由算法C的(ⅲ)～(ⅳ)可知圈u1u2…u4k-1u1中邊的標號有幾種情況:u2i-1u2i=|(4k+t-i)-(t+i-1)|=4k-2i+1,其中i=1,2,…,k;u2i-1u2i=|(4k+t-i-1)-(t+i-1)|=4k-2i,其中i=k+1,k+2,…,2k-1;u2iu2i+1=|[4k+t-(i+1)]-(t+i-1)|=4k-2i,其中i=1,2,…,k-1;u2iu2i+1=|[4k+t-(i+1)-1]-(t+i-1)|=4k-2i-1,其中i=k,k+1,…,2k-1;u4k-1u1=|(4k+t-2k-1)-(4k+t-1)|=2k.

首先,由(Ⅰ)易知,在路v1v2…vlu1中,邊的標號范圍為:4k+2≤v2i-1v2i≤4k+2t-2,其中i=1,2,…,t-1;4k+1≤v2iv2i+1≤4k+2t-3,其中i=1,2,…,t-1;v2t-1u1=4k.

由邊的標號范圍及奇偶性知,在路v1v2…vlu1中各邊的標號不相等.

其次,由(Ⅱ)易知, 在圈u1u2…u4k-1u1中,邊的標號范圍為:2k+1≤u2i-1u2i≤4k-1,其中i=1,2,…,k;2≤u2i-1u2i≤2k-2,其中i=k+1,k+2,…,2k-1;2k+2≤u2iu2i+1≤4k-2,其中i=1,2,…,k-1;1≤u2iu2i+1≤2k-1,其中i=k,k+1,…,2k-1;u4k-1u1=2k.

由邊的標號范圍及奇偶性知,在圈u1u2…u4k-1u1中各邊的標號不相等.

最后,由上易知,兩類邊的標號范圍互不重疊,故也互不相等.

綜上所述,當n=4k-1,l=2t-1時,棒棒糖圖Cn+Pl各邊的標號均不相同.即當n=4k-1,l=2t-1時,棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t-2}構(gòu)成一一對應.

由引理5、引理6及定義1知,情形3成立,即當n=4k-1,l=2t-1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

2.2情形4當n=4k-1,l=2t時,棒棒糖圖Cn+Pl是優(yōu)美圖.

當n=4k-1,l=2t時,棒棒糖圖Cn+Pl的頂點數(shù)為n+l=4k+2t-1,邊數(shù)為n+l=4k+2t-1.此時給出棒棒糖圖Cn+Pl的各頂點的標號遞推算法D如下:

(ⅰ)v2i-1=i-1,i=1,2,…,t.

(ⅱ)v2i=4k+2t-i,i=1,2,…,t.

(ⅲ)u2i-1=t+i-1,i=1,2,…,k; u2i-1=t+i,i=k+1,k+2,…,2k.

(ⅳ)u2i=4k+t-i,i=1,2,…,2k-1.

按照算法D可得以下結(jié)果:

引理7當n=4k-1,l=2t時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t-1}構(gòu)成單射.

證明當n=4k-1,l=2t時,記Q是棒棒糖圖Cn+Pl的所有頂點標號集合,由算法D的(ⅰ)～(ⅳ)易知:

Q1={v2i-1}={i-1|i=1,2,…,t}={0,1,…,t-1};

Q2={v2i}={4k+2t-i|i=1,2,…,t}={4k+t,4k+t+1,…,4k+2t-1};

Q3={u2i-1}={t+i-1|i=1,2,…,k}∪{t+i|i=k+1,k+2,…,2k}=

{t,t+1,…,t+k-1}∪{t+k+1,t+k+2,…,t+2k};

Q4={u2i}={4k+t-i|i=1,2,…,2k-1}={2k+t+1,2k+t+2,…,4k+t-1}.

易驗證,Qi∩Qj=?,i≠j且i,j=1,2,3,4.即當n=4k-1,l=2t時,棒棒糖圖Cn+Pl中各頂點的標號均不相同.又所有頂點標號的集合Q=Q1∪Q2∪Q3∪Q4中最小數(shù)是0(在Q1中),最大數(shù)是4k+2t-1(在Q2中),即當n=4k-1,l=2t時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t-1}構(gòu)成單射.

引理8當n=4k-1,l=2t時,棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t-1}構(gòu)成一一對應.

證明由算法D知,各頂點的標號中最小為零,最大為4k+2t-1,故邊的標號均不超過4k+2t-1.由算法D知,我們把邊的標號分為兩大類來考慮.

(Ⅰ)由算法D的(ⅰ)～(ⅲ)可知路v1v2…vlu1中邊的標號有幾種情況:v2i-1v2i=|(4k+2t-i)-(i-1)|=4k+2t-2i+1,其中i=1,2,…,t;v2iv2i+1=|(4k+2t-i)-[(i+1)-1]|=4k+2t-2i,其中i=1,2,…,t-1;v2tu1=|(4k+2t-t)-(t+1-1)|=4k.

(Ⅱ)由算法D的(ⅲ)～(ⅳ)可知圈u1u2…u4k-1u1中邊的標號有幾種情況:u2i-1u2i=|(4k+t-i)-(t+i-1)|=4k-2i+1,其中i=1,2,…,k;u2i-1u2i=|(4k+t-i)-(t+i)|=4k-2i,其中i=k+1,k+2,…,2k-1;u2iu2i+1=|(4k+t-i)-[t+(i+1)-1]|=4k-2i,其中i=1,2,…,k-1;u2iu2i+1=|(4k+t-i)-[t+(i+1)]|=4k-2i-1,其中i=k,k+1,…,2k-1;u4k-1u1=|(t+2k)-(t+1-1)|=2k.

首先,由(Ⅰ)易知,在路v1v2…vlu1中,邊的標號范圍為:4k+1≤v2i-1v2i≤4k+2t-1,其中i=1,2,…,t;4k+2≤v2iv2i+1≤4k+2t-2,其中i=1,2,…,t-1;v2tu1=4k.

由邊的標號范圍及奇偶性知,在路v1v2…vlu1中各邊的標號不相等.

其次,由(Ⅱ)易知,在圈u1u2…u4k-1u1中,邊的標號范圍為:2k+1≤u2i-1u2i≤4k-1,其中i=1,2,…,k;2≤u2i-1u2i≤2k-2,其中i=k+1,k+2,…,2k-1;2k+2≤u2iu2i+1≤4k-2,其中i=1,2,…,k-1;1≤u2iu2i+1≤2k-1,其中i=k,k+1,…,2k-1;u4k-1u1=2k.

由邊的標號范圍及奇偶性知,在圈u1u2…u4k-1u1中各邊的標號不相等.

最后,由上易知,兩類邊的標號范圍互不重疊,故也互不相等.

綜上所述,當n=4k-1,l=2t時,棒棒糖圖Cn+Pl各邊的標號均不相同.即當n=4k-1,l=2t時,棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t-1}構(gòu)成一一對應.

由引理7、引理8及定義1知,情形4成立,即當n=4k-1,l=2t時,棒棒糖圖Cn+Pl是優(yōu)美圖.

定理2當n=4k-1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

證明由情形3、情形4可知,定理2成立.

3定理3的證明

3.1情形5當n=4k+1,l=2t-1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

當n=4k+1,l=2t-1時,棒棒糖圖Cn+Pl的頂點數(shù)為n+l=4k+2t,邊數(shù)為n+l=4k+2t.分k≥t和k

當k≥t時,

(ⅰ)v2i-1=2k+t+i-1,i=1,2,…,t.

(ⅱ)v2i=2k+t-i,i=1,2,…,t-1.

(ⅲ)u1=2k;u2i-1=4k+2t-i+2,i=2,3,…,k+t+1; u2i-1=4k+2t-i+1,i=k+t+2,k+t+3,…,2k+1.

(ⅳ)u2i=i-1,i=1,2,…,2k.

當k

(ⅴ)v2i-1=2k+t+i-1,i=1,2,…,k;v2i-1=2k+t+i,i=k+1,k+2,…,t.

(ⅵ)v2i=2k+t-i,i=1,2,…,t-1.

(ⅶ)u1=2k,u2i-1=4k+2t-i+2,i=2,3,…,2k+1.

(ⅷ)u2i=i-1,i=1,2,…,2k.

按照算法E可得以下結(jié)果:

引理9當n=4k+1,l=2t-1時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t}構(gòu)成單射.

證明當n=4k+1,l=2t-1時,記R是棒棒糖圖Cn+Pl的頂點標號集合.當k≥t時,由算法E的(ⅰ)～(ⅳ)易知:

R1={v2i-1}={2k+t+i-1|i=1,2,…,t}={2k+t,2k+t+1,…,2k+2t-1};

R2={v2i}={2k+t-i|i=1,2,…,t-1}={2k+1,2k+2,…,2k+t-1};

R3={u1}∪{u2i-1|i=2,3,…,k+t+1}∪{u2i-1|i=k+t+2,k+t+3,…,2k+1}=

{2k}∪{4k+2t-i+2|i=2,…,k+t+1}∪{4k+2t-i+1|i=k+t+2,…,2k+1}=

{2k}∪{3k+t+1,3k+t+2,…,4k+2t}∪{2k+2t,2k+2t+1,…,3k+t-1};

R4={u2i}={i-1|i=1,2,…,2k}={0,1,…,2k-1}.

當k

R1={v2i-1}={2k+t+i-1|i=1,2,…,k}∪{2k+t+i|i=k+1,k+2,…,t}=

{2k+t,2k+t+1,…,3k+t-1}∪{3k+t+1,3k+t+2,…,2k+2t};

R2={v2i}={2k+t-i|i=1,2,…,t-1}={2k+1,2k+2,…,2k+t-1};

R3={u1}∪{u2i-1|i=2,3,…,2k+1}={2k}∪{4k+2t-i+2|i=2,3,…,2k+1}=

{2k}∪{2k+2t+1,2k+2t+2,…,4k+2t};

R4={u2i}={i-1|i=1,2,…,2k}={0,1,…,2k-1}.

不論k≥t還是k

引理10當n=4k+1,l=2t-1時,n=4k+1,l=2t-1的邊集與集合{1,2,3,…,4k+2t}構(gòu)成一一對應.

證明由引理9知,各頂點的標號中最小為零,最大為4k+2t,故邊的標號均不超過4k+2t.

當k≥t時,由算法E,我們把邊的標號分為兩大類來考慮.

(Ⅰ)由算法E的(ⅰ)～(ⅲ)可知路v1v2…vlu1中邊的標號有幾種情況:v2i-1v2i=|(2k+t+i-1)-(2k+t-i)|=2i-1,其中i=1,2,…,t-1;v2iv2i+1=|[2k+t+(i+1)-1]-(2k+t-i)|=2i,其中i=1,2,…,t-1;v2t-1u1=|(2k+t+t-1)-2k|=2t-1.

(Ⅱ)由算法E的(ⅲ)～(ⅳ)可知圈u1u2…u4k+1u1中邊的標號有幾種情況:u1u2=|2k-(1-1)|=2k;u2i-1u2i=|(4k+2t-i+2)-(i-1)|=4k+2t-2i+3,其中i=2,3,…,k+t+1;u2i-1u2i=|(4k+2t-i+1)-(i-1)|=4k+2t-2i+2,其中i=k+t+2,…,2k;u2iu2i+1=|[4k+2t-(i+1)+2]-(i-1)|=4k+2t-2i+2,其中i=1,2,…,k+t;u2iu2i+1=|[4k+2t-(i+1)+1]-(i-1)|=4k+2t-2i+1,其中i=k+t+1,…,2k;u4k+1u1=|[4k+2t-(2k+1)+1]-2k|=2t.

首先,由(Ⅰ)易知,在路v1v2…vlu1中,邊的標號范圍為:1≤v2i-1v2i≤2t-3,其中i=1,2,…,t-1;2≤v2iv2i+1≤2t-2,其中i=1,2,…,t-1;v2t-1u1=2t-1.

由邊的標號范圍及奇偶性知,在路v1v2…vlu1中各邊的標號不相等.

其次,由(Ⅱ)易知,在圈u1u2…u4k+1u1中,邊的標號范圍為:u1u2=2k;2k+1≤u2i-1u2i≤4k+2t-1,其中i=2,3,…,k+t+1;2t+2≤u2i-1u2i≤2k-2,其中i=k+t+2,…,2k;2k+2≤u2iu2i+1≤4k+2t,其中i=1,2,…,k+t;2t+1≤u2iu2i+1≤2k-1,其中i=k+t+1,…,2k;u4k+1u1=2t.

由邊的標號范圍及奇偶性知,在圈u1u2…u4k+1u1中各邊的標號不相等.

最后,由上易知,兩類邊的標號范圍互不重疊,故也互不相等.同理,當k

(Ⅲ)由算法E的(ⅴ)～(ⅶ)可知路v1v2…vlu1中邊的標號有幾種情況:v2i-1v2i=|(2k+t+i-1)-(2k+t-i)|=2i-1,其中i=1,2,…,k;v2i-1v2i=|(2k+t+i)-(2k+t-i)|=2i,其中i=k+1,k+2,…,t-1;v2iv2i+1=|[2k+t+(i+1)-1]-(2k+t-i)|=2i,其中i=1,2,…,k-1;v2iv2i+1=|[2k+t+(i+1)]-(2k+t-i)|=2i+1,其中i=k,k+1,…,t-1;v2t-1u1=|(2k+t+t)-2k|=2t.

(Ⅳ)由算法E的(ⅶ)～(ⅷ)可知圈u1u2…u4k+1u1中邊的標號有幾種情況:u1u2=|2k-(1-1)|=2k;u2i-1u2i=|(4k+2t-i+2)-(i-1)|=4k+2t-2i+3,其中i=2,3,…,2k;u2iu2i+1=|[4k+2t-(i+1)+2]-(i-1)|=4k+2t-2i+2,其中i=1,2,…,2k;u4k+1u1=|[4k+2t-(2k+1)+2]-2k|=2t+1.

首先,由(Ⅲ)易知,在路v1v2…vlu1中,邊的標號范圍為:1≤v2i-1v2i≤2k-1,其中i=1,2,…,k;2k+2≤v2i-1v2i≤2t-2,其中i=k+1,k+2,…,t-1;2≤v2iv2i+1≤2k-2,其中i=1,2,…,k-1;2k+1≤v2iv2i+1≤2t-1,其中i=k,k+1,…,t-1;v2t-1u1=2t.

由邊的標號范圍及奇偶性知,在路v1v2…vlu1中各邊的標號不相等.

其次,由(Ⅳ)易知,在圈u1u2…u4k+1u1中,邊的標號范圍為:u1u2=2k;2t+3≤u2i-1u2i≤4k+2t-1,其中i=2,3,…,2k;2t+2≤u2iu2i+1≤4k+2t,其中i=1,2,…,2k;u4k+1u1=2t+1.

由邊的標號范圍及奇偶性知,在圈u1u2…u4k+1u1中各邊的標號不相等.

最后,由上易知,兩類邊的標號范圍互不重疊,故也互不相等.

綜上所述,當n=4k+1,l=2t-1時,不論k≥t還是k

由引理9、引理10及定義1知,情形5成立,即當n=4k+1,l=2t-1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

3.2情形6當n=4k+1,l=2t且k≤t時,棒棒糖圖Cn+Pl是優(yōu)美圖．

當n=4k+1,l=2t且k≤t時,棒棒糖圖Cn+Pl的頂點數(shù)為n+l=4k+2t+1,邊數(shù)為n+l=4k+2t+1.給出棒棒糖圖Cn+Pl的各頂點的標號遞推算法F如下:

(ⅰ)v2i-1=2k+t-i+2,i=1,2,…,k; v2i-1=2k+t-i+1,i=k+1,k+2,…,t.

(ⅱ)v2i=2k+t+i+1,i=1,2,…,t.

(ⅲ)u1=2k;u2i-1=4k+2t-i+3,i=2,3,…,2k+1.

(ⅳ)u2i=i-1,i=1,2,…,2k.

按照算法F可得以下結(jié)果:

引理11當n=4k+1,l=2t且k≤t時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t+1}構(gòu)成單射.

證明當n=4k+1,l=2t且k≤t時,記S是棒棒糖圖Cn+Pl的頂點標號集合,由算法F的(ⅰ)～(ⅳ)易知:

S1={v2i-1}={2k+t-i+2|i=1,2,…,k}∪{2k+t-i+1|i=k+1,k+2,…,2t}=

{k+t+2,k+t+3,…,2k+t+1}∪{2k+1,2k+2,…,k+t};

S2={v2i}={2k+t+i+1|i=1,2,…,t}={2k+t+2,2k+t+3,…,2k+2t+1};

S3={u2i-1}={u1}∪{u2i-1|i=2,3,…,2k+1}=

{2k}∪{4k+2t-i+3|i=2,3,…,2k+1}=

{2k}∪{2k+2t+2,2k+2t+3,…,4k+2t+1};

S4={u2i}={i-1|i=1,2,…,2k}={0,1,…,2k-1}.

易驗證,Si∩Sj=?,i≠j且i,j=1,2,3,4.即當n=4k+1,l=2t且k≤t時,棒棒糖圖Cn+Pl中各頂點的標號均不相同.又所有頂點標號的集合S=S1∪S2∪S3∪S4中最小數(shù)是0(在S4中),最大數(shù)4k+2t+1(在S3中).所以,當n=4k+1,l=2t且k≤t時,棒棒糖圖Cn+Pl的頂點集與集合{0,1,2,…,4k+2t+1}構(gòu)成單射.

引理12當n=4k+1,l=2t且k≤t時,棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t+1}構(gòu)成一一對應.

證明由算法F知,各頂點的標號中最小為零,最大為4k+2t+1,故邊的標號均不超過4k+2t+1.我們把邊的標號分為兩大類來考慮.

(Ⅰ)由算法F的(ⅰ)～(ⅲ)可知路v1v2…vlu1中邊的標號有幾種情況:v2i-1v2i=|(2k+t+i+1)-(2k+t-i+2)|=2i-1,其中i=1,2,…,k;v2i-1v2i=|(2k+t+i+1)-(2k+t-i+1)|=2i,其中i=k+1,k+2,…,t;v2iv2i+1=|(2k+t+i+1)-[2k+t-(i+1)+2]|=2i,其中i=1,2,…,k-1;v2iv2i+1=|(2k+t+i+1)-[2k+t-(i+1)+1]|=2i+1,其中i=k,k+1,…,t-1;v2tu1=|(2k+t+t+1)-2k|=2t+1.

(Ⅱ)由算法F的(ⅲ)～(ⅳ)可知圈u1u2…u4k+1u1中邊的標號有幾種情況:u1u2=|2k-(1-1)|=2k;u2i-1u2i=|(4k+2t-i+3)-(i-1)|=4k+2t-2i+4,其中i=1,2,…,2k;u2iu2i+1=|[4k+2t-(i+1)+3]-(i-1)|=4k+2t-2i+3,其中i=1,2,…,2k;u4k+1u1=|[4k+2t-(2k+1)+3]-2k|=2t+2.

首先,由(Ⅰ)易知,在路v1v2…vlu1中,邊的標號范圍為:1≤v2i-1v2i≤2k-1,其中i=1,2,…,k;2k+2≤v2i-1v2i≤2t,其中i=k+1,k+2,…,t;2≤v2iv2i+1≤2k-2,其中i=1,2,…,k-1;2k+1≤v2iv2i+1≤2t-1,其中i=k,k+1,…,t-1;v2t-1u1=2t+1.

由邊的標號范圍及奇偶性知,在路v1v2…vlu1中各邊的標號不相等.

其次,由(Ⅱ)易知,在圈u1u2…u4k+1u1中,邊的標號范圍為:u1u2=2k;2t+4≤u2i-1u2i≤4k+2t,其中i=2,3,…,2k;2t+3≤u2iu2i+1≤4k+2t+1,其中i=1,2,…,2k;u4k+1u1=2t+2.

由邊的標號范圍及奇偶性知,在圈u1u2…u4k+1u1中各邊的標號不相等.

最后,由上易知,兩類邊的標號范圍互不重疊,故也互不相等.

綜上所述,當n=4k+1,l=2t且k≤t時,棒棒糖圖Cn+Pl各邊的標號均不相同.即當n=4k+1,l=2t且k≤t時,棒棒糖圖Cn+Pl的邊集與集合{1,2,3,…,4k+2t+1}構(gòu)成一一對應.

由引理11、引理12及定義1知,情形6成立,即當n=4k+1,l=2t且k≤t時,棒棒糖圖Cn+Pl是優(yōu)美圖.

定理3當n=4k+1時,棒棒糖圖Cn+Pl是優(yōu)美圖.

證明由情形5、情形6及定義1可知,定理3成立.

參考文獻：

[1]RINGELG.Problem25,in:theoryofgraphsanditsapplication[J].ProcSymposiumSmolenice, 1963,1263: 162-167.

[2]GALLIANJA.Adynamicsurveyofgraphlabeling[J].TheElectronicJournalofCombinatorics, 2009, 16(6): 6-27.

[5] 林育青.一類圖的優(yōu)美性[J].云南師范大學學報(自然科學版),2004,24(4):15-19.

[6] 林育青.Cn與1Cn的優(yōu)美標號[J].安徽大學學報(自然科學版),2007,32(2):13-16.

[7] 張玲瑛,林育青,鐘發(fā)勝,等.關(guān)于圖2×Cn的標號[J].北華大學學報(自然科學版),2014,15(2):174-178.

[9] 馬克杰.優(yōu)美圖[M].北京:北京大學出版社,1991：54-55.

[10] 陳暑波,夏方禮,龍韜，等.棒棒糖圖的Merrifield-Simmons和Hosoya指數(shù)[J]. 湖南城市學院學報(自然科學版),2008,17(3):39-41.

[11]BANDYJA,MURTYUSR.Graphtheorywithapplication[M].NewYork:AmericanElsevierPublishingCoInc, 1976.

收稿日期：2015-10-11

基金項目:汕頭職業(yè)技術(shù)學院2015年院級科研課題(SZK2015Y23).

作者簡介:童細心,男,湖南岳陽人,汕頭職業(yè)技術(shù)學院自然科學系講師.

中圖分類號：O157.5

文獻標識碼：A

文章編號：2095-3798(2016)03-0048-09

The Gracefulness of Lollipop Graphs

TONG Xi-xin

(Department of Natural Sciences, Shantou Polytechnic, Shantou, Guangdong, 515041, P.R.China)

Abstract:Graceful labeling algorithm of lollipop graphs Cn+Plare given when n=4k,4k-1,4k+1, and the conclusion is obtained that lollipop graphs Cn+Plare Graceful graph when n=4k,4k-1,4k+1.

Key words:lollipop graphs; graceful labeling; graceful graph