吳躍生,李詠秋

(1.華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西南昌330013;2.華東交通大學(xué)圖書館,江西南昌 330013)

關(guān)于圈C3的(1,2a,2a+1)-冠的優(yōu)美性研究

吳躍生1,李詠秋2

(1.華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西南昌330013;2.華東交通大學(xué)圖書館,江西南昌 330013)

給出了圈Cn的(r1,r2,…,rn)-冠的定義,討論了圈C3的(1,2a,2a+1)-冠的優(yōu)美性,用構(gòu)造性方法給出了圈C3的(1,2a,2a+1)-冠的優(yōu)美標(biāo)號(hào).

圈;冠;r-冠;優(yōu)美標(biāo)號(hào);優(yōu)美圖

1 概念

本文所討論的圖均為無向簡(jiǎn)單圖,V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集,未說明的符號(hào)及術(shù)語均同文獻(xiàn)[1].

定義1[1]對(duì)于一個(gè)圖G=(V,E)如果存在一個(gè)單射θ:V(G)→{0,1,2,…,|E(G)|},使得對(duì)所有邊e=(u,v)∈E(G),由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的E(G)→{1,2,…,|E(G)|}是一個(gè)雙射,則稱G是優(yōu)美圖,θ是G的一組優(yōu)美標(biāo)號(hào),稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎ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)-冠.特別地,當(dāng)r1=r2=…rn=r時(shí),稱為圖G的r-冠.圖G的0-冠就是圖G.

馬克杰等在文獻(xiàn)[1]中證明了圖P1∨Pn的優(yōu)美性,并證明了圖P1∨Pn的r-冠的優(yōu)美性,由此猜想:任意優(yōu)美圖的r-冠都是優(yōu)美圖.

文獻(xiàn)[2-5]在上述猜想的引導(dǎo)下,證明了一些優(yōu)美圖(如圈Cn(n≡0,3(mod 4)))的r-冠是優(yōu)美的.文獻(xiàn)[6]證明了一些特殊的圈Cn的(r1,r2,…,rn)-冠(當(dāng)n=7,8時(shí))是優(yōu)美圖.

本文給出了圈Cn的(r1,r2,…,rn)-冠的定義,討論圈C3的(1,2a,2a+1)-冠的優(yōu)美性,用構(gòu)造性方法給出圈C3的(1,2a,2a+1)-冠的優(yōu)美標(biāo)號(hào).

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

定理 設(shè)圈C3的(1,2a,2a+1)-冠的頂點(diǎn)集如圖1所示,當(dāng)a≥0時(shí),圈C3的(1,2a,2a+1)-冠是優(yōu)美圖.

證明設(shè)圈C3的(1,2a,2a+1)-冠的頂點(diǎn)集如圖1所示.

圖1 圈C3的(1,2a,2a+1)-冠的頂點(diǎn)集

如圖2所示,定義圈C3的(1,2a,2a+1)-冠的頂點(diǎn)標(biāo)號(hào)θ為θ(v1)=4a+4,θ(v2)=0,θ(v3)=4a+5, θ(v4)=a+2,θ(x1i)=i,i=1,2,…,a+1,θ(x1i)=2a+1+i,i=a+2,a+3,…,2a+1,θ(x3i)=a+2+i,i= 1,2,…,2a.

容易驗(yàn)證,θ:V(圈C3的(1,2a,2a+1)-冠)→{0,1,2,…,4a+5}是一個(gè)單射.

因此,θ是圈C3的(1,2a,2a+1)-冠的優(yōu)美標(biāo)號(hào),即圈C3的(1,2a,2a+1)-冠是優(yōu)美圖.

下面根據(jù)定理給出當(dāng)a=3時(shí),圈C3的(1,2a,2a+1)-冠的優(yōu)美標(biāo)號(hào)如圖3所示.

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

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

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

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

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

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

Research on Gracefulness of the(1,2a,2a+1)-Corona of CycleC3

WU Yue-sheng1,L I Yong-qiu2

(1.School of Basic Science,East China Jiaotong University,Nanchang330013,China; 2.Library,East China Jiaotong University,Nanchang330013,China)

A definition is given to the(r1,r2,…,rn)-corona of cycleCn.The gracefulnessof the(1,2a,2a+1)-corona of cycleC3is discussed.The graceful labeling of the(1,2a,2a+1)-corona of cycleC3is given by a constructive method.

cycle;corona;r-corona;graceful labeling;graceful graph

O157.5

A

1007-0834(2010)04-0001-02

10.3969/j.issn.1007-0834.2010.04.001

2010-07-25

國家自然科學(xué)基金(11061014)

吳躍生(1959—),男,江西瑞金人,華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院副教授,研究方向:圖論.