圖ω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)號(hào)。證明了一些特殊的ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠是交錯(cuò)圖。

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

1 引言與概念

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

文中所討論的圖均為無(wú)向簡(jiǎn)單圖，V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集，未說(shuō)明的符號(hào)及術(shù)語(yǔ)均見(jiàn)文［1］。

定義1［1］對(duì)于一個(gè)簡(jiǎn)單圖G=V(G),E(G)=(V,E)，如果對(duì)每一個(gè)頂點(diǎn)v∈V，存在一個(gè)非負(fù)整數(shù)θ(v)（稱為頂點(diǎn)v的標(biāo)號(hà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)號(hào)），則G稱為優(yōu)美圖，θ(v)稱為G的一個(gè)優(yōu)美標(biāo)號(hào)。

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

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

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

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

文獻(xiàn)［1］中證明了P1∨Pn及其r-冠是優(yōu)美的，從而猜測(cè)：任意優(yōu)美圖的r-冠都是優(yōu)美的，在此猜想的指導(dǎo)下，文獻(xiàn)［3-5］中證明了：當(dāng)n≡0,3(mod4)時(shí)，圖Cn及其r-冠是優(yōu)美圖；文獻(xiàn)［6-8］中給出了圖Cn的(r1,r2,...,rn)-冠的定義，討論了n=3,7,8,11,4h,4h+3時(shí)，圖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)時(shí)，圖ωm,n的(r1,r2,...,rm+n-1)-冠的優(yōu)美性。本文證明了圖ω4g,4h+3的(r1,r2,...,r4g+4h+2)-冠的優(yōu)美性，并給出了4種不同的優(yōu)美標(biāo)號(hào)，同時(shí)證明了這些優(yōu)美標(biāo)號(hào)也是交錯(cuò)標(biāo)號(hà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)-冠的頂點(diǎn)集如圖1所示，V(ωm,n)=(v1,v2,...,vm,vm+1,...,vm+n-1)，與vi鄰接的懸掛邊（或葉）記為xij（vi∈V(ωm,n)，j=1,2,...,ri），當(dāng)時(shí)，ωm,n的(r1,r2,...,rm+n-1)-冠是優(yōu)美圖且為交錯(cuò)圖。

圖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)美（交錯(cuò)）標(biāo)號(hào)：

容易驗(yàn)證：

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

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

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

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

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

例下面根據(jù)定理給出ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2)-冠的4種交錯(cuò)標(biāo)號(hà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種交錯(cuò)標(biāo)號(hà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種交錯(cuò)標(biāo)號(hà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種交錯(cuò)標(biāo)號(hà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種交錯(cuò)標(biāo)號(hà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錯(cuò)圖并的優(yōu)美性[J].吉林工程技術(shù)師范學(xué)院學(xué)報(bào):自然科學(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é)報(bào)2000,22(4):4-7.

[5]胡紅亮.圖Cn的r-冠的新的優(yōu)美標(biāo)號(hà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].阜陽(yáng)師范學(xué)院學(xué)報(bào):自然科學(xué)版,2010,27(3):20-23.

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

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

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

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

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

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

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

[14]吳躍生,王廣富,徐保根.關(guān)于圖C4h+1⊙k1的(Gr1,Gr2,Gr3,...,Gr4h+2)-冠的優(yōu)美性[J].山東大學(xué)學(xué)報(bào):理學(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

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

張政（1981—），男，講師，研究方向?yàn)閳D論及其應(yīng)用。

1005-0523（2014）05-0117-05