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

吳躍生,李詠秋

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

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

吳躍生1,李詠秋2

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

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

圈;冠;r-冠;優(yōu)美標號;優(yōu)美圖

1 概念

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

定義1[1]對于一個圖G=(V,E)如果存在一個單射θ:V(G)→{0,1,2,…,|E(G)|},使得對所有邊e=(u,v)∈E(G),由θ′(e)=|θ(u)-θ(v)|導出的E(G)→{1,2,…,|E(G)|}是一個雙射,則稱G是優(yōu)美圖,θ是G的一組優(yōu)美標號,稱θ′為G的邊上的由θ導出的誘導值.

定義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)-冠.特別地,當r1=r2=…rn=r時,稱為圖G的r-冠.圖G的0-冠就是圖G.

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

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

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

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

定理 設圈C3的(1,2a,2a+1)-冠的頂點集如圖1所示,當a≥0時,圈C3的(1,2a,2a+1)-冠是優(yōu)美圖.

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

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

如圖2所示,定義圈C3的(1,2a,2a+1)-冠的頂點標號θ為θ(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.

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

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

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

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

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

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

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

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

[6] 吳躍生,李詠秋.關(guān)于圈Cn的(r1,r2,…,rn)-冠(n=7,8)的優(yōu)美性[J].阜陽師范學院學報:自然科學版,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

國家自然科學基金(11061014)

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