关于圈C3的(1,2a,2a+1)-冠的优美性研究

吴跃生,李咏秋

(1.华东交通大学基础科学学院,江西南昌330013;2.华东交通大学图书馆,江西南昌 330013)

关于圈C3的(1,2a,2a+1)-冠的优美性研究

吴跃生1,李咏秋2

(1.华东交通大学基础科学学院,江西南昌330013;2.华东交通大学图书馆,江西南昌 330013)

给出了圈Cn的(r1,r2,…,rn)-冠的定义,讨论了圈C3的(1,2a,2a+1)-冠的优美性,用构造性方法给出了圈C3的(1,2a,2a+1)-冠的优美标号.

圈;冠;r-冠;优美标号;优美图

1 概念

本文所讨论的图均为无向简单图,V(G)和E(G)分别表示图G的顶点集和边集,未说明的符号及术语均同文献[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是优美图,θ是G的一组优美标号,称θ′为G的边上的由θ导出的诱导值.

定义2[1]在图G每个顶点都粘接了r条悬挂边(r≥1的整数)所得到的图称为图G的r-冠.图G的1-冠称为图G的冠.

定义3V(G)=(v1,v2,…,vn)的每个顶点vi都粘接了ri条悬挂边(ri≥0的整数,i=1,2,…,n)所得到的图,称为图G的(r1,r2,…,rn)-冠.特别地,当r1=r2=…rn=r时,称为图G的r-冠.图G的0-冠就是图G.

马克杰等在文献[1]中证明了图P1∨Pn的优美性,并证明了图P1∨Pn的r-冠的优美性,由此猜想:任意优美图的r-冠都是优美图.

文献[2-5]在上述猜想的引导下,证明了一些优美图(如圈Cn(n≡0,3(mod 4)))的r-冠是优美的.文献[6]证明了一些特殊的圈Cn的(r1,r2,…,rn)-冠(当n=7,8时)是优美图.

本文给出了圈Cn的(r1,r2,…,rn)-冠的定义,讨论圈C3的(1,2a,2a+1)-冠的优美性,用构造性方法给出圈C3的(1,2a,2a+1)-冠的优美标号.

2 主要结果及其证明

定理 设圈C3的(1,2a,2a+1)-冠的顶点集如图1所示,当a≥0时,圈C3的(1,2a,2a+1)-冠是优美图.

证明设圈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)-冠的优美标号,即圈C3的(1,2a,2a+1)-冠是优美图.

下面根据定理给出当a=3时,圈C3的(1,2a,2a+1)-冠的优美标号如图3所示.

[1] 马克杰.优美图[M].北京:北京大学出版社,1991.

[2] 武建春.图D2,4k与它的r-冠的优美性[J].内蒙古电大学刊,2002(1):34.

[3] 曾朝英,武建春.关于优美图Cn和Cn⊙k1的r-冠的优美性[J].集宁师专学报,2000,22(4):4-7.

[4] 曾朝英.图ω4k,n的r-冠的优美性[J].集宁师专学报,2001,23(4):4-6.

[5] 胡红亮.图Cn及其r-冠的新的优美标号[J].纯粹数学与应用数学,2010,26(3):454-457.

[6] 吴跃生,李咏秋.关于圈Cn的(r1,r2,…,rn)-冠(n=7,8)的优美性[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—),男,江西瑞金人,华东交通大学基础科学学院副教授,研究方向:图论.