圖ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的優(yōu)美性

張政，胡紅亮

（西安航空學(xué)院理學(xué)院，陜西西安710077）

圖ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的優(yōu)美性

張政，胡紅亮

（西安航空學(xué)院理學(xué)院，陜西西安710077）

給出了ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的定義，討論了ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的優(yōu)美性，用構(gòu)造性的方法給出了一些特殊的ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的優(yōu)美標(biāo)號。證明了一些特殊的ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠是交錯圖。

圈；冠；優(yōu)美圖；交錯圖

1 引言與概念

優(yōu)美圖是圖論中極有趣的研究課題，有著較好的應(yīng)用價值和廣闊的研究前景。它的研究是從1963年GRingel提出的一個猜想和1966年A Rosa的一篇論文開始的。1972年，SW Golomb明確給出了優(yōu)美圖的定義。近幾十年，國內(nèi)外獲得不少關(guān)于優(yōu)美圖的研究成果，它們被應(yīng)用于射電天文學(xué)，X-射線衍射晶體學(xué)，密碼設(shè)計，通信網(wǎng)絡(luò)編址，導(dǎo)彈控制碼設(shè)計，同步機碼設(shè)計等領(lǐng)域。

文中所討論的圖均為無向簡單圖，V(G)和E(G)分別表示圖G的頂點集和邊集，未說明的符號及術(shù)語均見文［1］。

定義1［1］對于一個簡單圖G=V(G),E(G)=(V,E)，如果對每一個頂點v∈V，存在一個非負(fù)整數(shù)θ(v)（稱為頂點v的標(biāo)號）使?jié)M足：

①?u,v∈V，若u≠v，則θ(u)≠θ(v)。②max{θ(v)|v∈V}=|E|。③?e1,e2∈E，若e1≠e2，則θ'(e1)≠θ'(e2)。其中：θ'(e)=|θ(u)-θ(v)|，e=uv（稱θ'(e)為邊e的標(biāo)號），則G稱為優(yōu)美圖，θ(v)稱為G的一個優(yōu)美標(biāo)號。

定義2［1］在圖G每個頂點都粘接了r條懸掛邊（r≥1的整數(shù)）所得到的圖，稱為圖G的r-冠，圖G的1-冠，稱作圖G的冠。

定義3V(G)={v1,v2,...,vn}的每個頂點vi都粘接了ri條懸掛邊（ri≥0的整數(shù)，i=1,2,...,n）所得到的圖，稱為圖G的(r1,r2,...,rn)-冠，簡記為G(r1,r2,...,rn)。特別地，當(dāng)r1=r2=...=rn=r時，稱為圖G的r-冠。圖G的0-冠就是圖G。

定義4［1］由圈Cm和Cn恰有一個公共點所組成的圖記為圖ωm,n。

定義5［2］G是一個優(yōu)美二部圖，其優(yōu)美標(biāo)號為θ，V(G)劃分成兩個集合X,Y，如果maxθ(v)＜minθ(v)，則稱θ是G的交錯標(biāo)號，稱G是在交錯標(biāo)號θ下的交錯圖。

文獻(xiàn)［1］中證明了P1∨Pn及其r-冠是優(yōu)美的，從而猜測：任意優(yōu)美圖的r-冠都是優(yōu)美的，在此猜想的指導(dǎo)下，文獻(xiàn)［3-5］中證明了：當(dāng)n≡0,3(mod4)時，圖Cn及其r-冠是優(yōu)美圖；文獻(xiàn)［6-8］中給出了圖Cn的(r1,r2,...,rn)-冠的定義，討論了n=3,7,8,11,4h,4h+3時，圖Cn的(r1,r2,...,rn)-冠的優(yōu)美性；文獻(xiàn)［10-12］給出了ωm,n的(r1,r2,...,rm+n-1)-冠的定義，討論了(m,n)=(4,4),(4,6),(5,6),(5,7)時，圖ωm,n的(r1,r2,...,rm+n-1)-冠的優(yōu)美性。本文證明了圖ω4g,4h+3的(r1,r2,...,r4g+4h+2)-冠的優(yōu)美性，并給出了4種不同的優(yōu)美標(biāo)號，同時證明了這些優(yōu)美標(biāo)號也是交錯標(biāo)號。

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

定理當(dāng)m=4g，n=4h+3，g和h為任意自然數(shù)，ri為任意非負(fù)整數(shù)（i=1,2,...,m+n-1），圖ωm,n的(r1,r2,...,rm+n-1)-冠的頂點集如圖1所示，V(ωm,n)=(v1,v2,...,vm,vm+1,...,vm+n-1)，與vi鄰接的懸掛邊（或葉）記為xij（vi∈V(ωm,n)，j=1,2,...,ri），當(dāng)時，ωm,n的(r1,r2,...,rm+n-1)-冠是優(yōu)美圖且為交錯圖。

圖1 ω4g,4h+3的(r1,r2,...,r4g+4h+2)-冠Fig.1 The(r1,r2,...,r4g+4h+2)-corona of the graphω4g,4h+3

第1種優(yōu)美（交錯）標(biāo)號：

容易驗證：

θ:V（ω4g,4h+3的() r1,r2,...,r4g+4h+2-冠）→是一個單射。

因此，θ是ω4g,4h+3的(r1,r2,...,r4g+4h+2)-冠的交錯標(biāo)號。即ω4g,4h+3的(r1,r2,...,r4g+4h+2)-冠是交錯圖。第2種優(yōu)美（交錯）標(biāo)號：

第3種優(yōu)美（交錯）標(biāo)號：

第4種優(yōu)美（交錯）標(biāo)號：

第2、3、4種優(yōu)美交錯標(biāo)號的證明類似于第1種優(yōu)美交錯標(biāo)號，此處略。

例下面根據(jù)定理給出ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2)-冠的4種交錯標(biāo)號，如圖2～圖5所示。

圖2 圖ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2) -冠的第1種交錯標(biāo)號Fig.2 The firstalternating labeling of the (1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2) -corona of the graphω8,11

圖3 圖ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2) -冠的第2種交錯標(biāo)號Fig.3 The second alternating labeling of the (1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2) -corona of the graphω8,11

圖4 圖ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2)-冠的第3種交錯標(biāo)號Fig.4 The third alternating labeling of the(1,2,3,2, 3,1,1,2,2,1,3,2,1,2,1,2,3,2)-corona of the graphω8,11

圖5 圖ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2)-冠的第4種交錯標(biāo)號Fig.5 The fourth alternating labeling of the(1,2,3,2, 3,1,1,2,2,1,3,2,1,2,1,2,3,2)-corona of the graphω8,11

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

[2]楊顯文,張志尚.一類交r錯圖并的優(yōu)美性[J].吉林工程技術(shù)師范學(xué)院學(xué)報:自然科學(xué)版,2007,23(6):8-10.

[3]武建春.圖D2,4k與它的-冠的優(yōu)美性[J].內(nèi)蒙古電大學(xué)刊,2002(1):34.

[4]曾朝英,武建春.關(guān)于優(yōu)美圖Cn和r¤k1的r-冠的優(yōu)美性[J].集寧師專學(xué)報2000,22(4):4-7.

[5]胡紅亮.圖Cn的r-冠的新的優(yōu)美標(biāo)號[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)[J].2010,26(3):454-457.

[6]吳躍生,李詠秋.關(guān)于圈Cn的(r1,r2,...,rn)-冠(n=7,8)的優(yōu)美性[J].阜陽師范學(xué)院學(xué)報:自然科學(xué)版,2010,27(3):20-23.

[7]吳躍生,李詠秋.再探圈Cn的(r1,r2,...,rn)-冠(n=7,8)的優(yōu)美性[J].阜陽師范學(xué)院學(xué)報:自然科學(xué)版,2010,27(4):1-4.

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

[9]曾朝英.圖ω4k,n的r-冠的優(yōu)美性[J].集寧師專學(xué)報,2001,23(4):4-6.

[10]吳躍生,李詠秋.關(guān)于圖ω4,4的(r1,r2,...,r7)-冠的優(yōu)美性[J].宜春學(xué)院學(xué)報,2010,32(12):1-3.

[11]吳躍生.關(guān)于圖ω4,6的(r1,r2,...,r9)-冠的優(yōu)美性[J].宜春學(xué)院學(xué)報,2011,33(8):1-3.

[12]吳躍生,李詠秋.關(guān)于圖ω5,6的(r1,r2,...,r10)-冠的優(yōu)美性[J].北京聯(lián)合大學(xué)學(xué)報,2011,25(2):60-61.

[13]吳躍生,李詠秋.關(guān)于圖ω5,7的(r1,r2,...,r11)-冠的優(yōu)美性[J].嘉應(yīng)學(xué)院學(xué)報,2011,29(5):5-8.

[14]吳躍生,王廣富,徐保根.關(guān)于圖C4h+1⊙k1的(Gr1,Gr2,Gr3,...,Gr4h+2)-冠的優(yōu)美性[J].山東大學(xué)學(xué)報:理學(xué)版,2013,48(4):25-28.

On the Gracefulnessof the() r1,r2,...,r4g+4h+2-corona of the Graphω4g,4h+3

Zhang Zheng,Hu Hongliang
(Schoolof Science,Xi’an AeronauticalUniversity,Xi’an 710077,China)

A definition hasbeen given for the(r1,r2,...,r4g+4h+2) -corona of the graphω4g,4h+3.The gracefulnessof the (r1,r2,...,r4g+4h+2) -corona of the graphω4g,4h+3is then discussed and the graceful labeling is presented in this paper. Italso proves thatsome special(r1,r2,...,r4g+4h+2) -corona of the graphω4g,4h+3are ofalternating graph.

cycle;corona;gracefulgraph;alternating graph

O157.5

A

2014-06-23

國家自然科學(xué)基金（11171273）

張政（1981—），男，講師，研究方向為圖論及其應(yīng)用。

1005-0523（2014）05-0117-05