一类链图的优美性研究

摘要:该文首先给出了四圈链图的一种新的优美标号,讨论了四圈链图与路的一个端点相粘得到的一类图的优美性和交错性,在此基础上研究了两个四圈链图与路的两个端点分别相粘得到的一类图的优美性。

关键词:优美标号;优美图;交错图;

中图分类号:O157.5文献标识码:A文章编号:1009-3044(2010)19-5280-03

The Beauty of a Class Study of Chain Graph

WANG Tian-cheng

(Maths Department, Normal College of Minority Nationalities of Qinghai Normal University, Xining 810008, China)

Abstract: This paper gives the four-ring chain Figure graceful labeling of a new, four-ring chains are discussed and the road map with one end sticking by the beauty of a class diagram and staggered nature of this basis, two Four circle chain map and the road with two sticky ends were obtained by the beauty of a class diagram.

Key words: graceful labeling; graceful graph; alternating graph

1 预备知识

定义1[2] 设G=(V,E)是n阶m条边的简单图。若存在一个映射f:V{0,1,2…m},满足①f是单射;②max{f(v),v∈V}=m;③设e=uv∈E,令f(uv) =|f(u)-F(v)|;④{f(uv)|uv∈E}={1,2,3…m},则称f为G的一个优美标号(gracefullabelingn),此时称G为优美图。

定义2 设H(v)是二分图G(X,Y;E),f是G的一个优美标号,且满足: 则称H(v)是G的一个交错标号。若G有一个交错标号,则G是交错二分图。

定义3将C4中不相邻的两个边分别定义为始边和终边,则由m个C4的始边和终边依次链接而成的图称为C4链图,记作m*C4。

引理1m*C4是优美图且是交错图

证明:如图1标出其顶点顺序,令C4链图中各顶点标号如下:

1)当m为奇数时:

容易验证:f(V)为其优美标号。(略)

令X=P∪Q,Y=R∪S

其中P={A4i+1},Q={A4i+2},R={A4i},S={A4i+3}

因为X中的顶点互不相邻,Y中的顶点也互不相邻且

所以当m为奇数时,m*C4是优美图且是交错图。

2)当m为偶数时:

所以当m为偶数时,m*C4是优美图且是交错图。

2 主要结论及证明

定义4 将m*C4的点A2m+1与Pn(表示有奇数个顶点n的路)的终点Vn (m为奇数时) 粘接或将A2m与Pn的终点Vn (m为偶数时) 粘接而成的图记作T(m*C4,Pn)。

定理1 T(m*C4,Pn)是优美图且是交错图。

图2T(m*C4,Pn)m为奇数

图3 T(m*C4,Pn)m为偶数

证明:m为奇数时如图2标出其顶点顺序,令R(m=C4,Pn)图中各顶点标号如下:

其中[n/2]表示不超过n/2的最大整数。

容易验证:f(v)为其优美标号。(略)

令X1=P∪Q,Y1=R∪S

其中P={A4i+1},Q={A4i+2},R={A4i},S={A4i+3}

X2={V2i},Y2={V2i-1}

因为X=X1∪X2中的顶点互不相邻,Y=Y1∪Y2中的顶点也互不相邻且

所以R(m*C4,Pn)是优美图且是交错图。

为偶数时如图3标出其顶点顺序。同法可证。

定义5用Pn(表示有奇数个顶点n的路)的两个端点V1和Vn将m*C4和s*C4的A0和B0分别粘接而成的图记作E(m*C4,Pn, s*C4)。

图4 E(m*C4,Pn, s*C4)m为奇数

图5 E(m*C4,Pn, s*C4)m为偶数

定理2 E(m*C4,Pn, s*C4)是优美图。

证明:m为奇数时如图4标出其顶点顺序,令图D(m*C4,Pn, s*C4)中各顶点标号如下:

下面证明上述标号为优美标号:

1)显然在f(v)标号下m*C4各顶点的标号各不相同,Pn和s*C4中的各顶点的标号也各不相同。在f(v)下除f(B0)=f(V1),f(A2m+1)=f(Vn)外再没有标号相同的点,而B0与V1是重合点,A2m+1与Vn是重合点,因此E(m*C4,Pn, s*C4)内顶点不同时标号也不同。而且f(v)中标号最小为0,最大为f(A1)=E的边数=3m+3s+1+n,即最大值为D的边数。

2)在f(v)标号下s*C4各边的标号从1~3s+1各不相同,Pn各边的标号从3s+2～3s+n+1各不相同,m*C4各边的标号从3s+n+2～3s+n+3m+1各不相同即边标号集合为{1,2,3…,3s+3m+n+1},故E(m*C4,Pn, s*C4)是优美图。

m为偶数时如图5标出其顶点顺序,同法可证。

参考文献:

[1] Bondy J A,Murty U S R.图论及其应用[M].吴望名,译.北京:科学出版社,1984.

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

[3] 王天成,张秉儒.关于图D(m=C4,Pn,s=C4)优美性的研究[J].青海师范大学学报:自然科学版,2008(1):12-14.

[4] 李春香.关于R=(m=C4,C4k-1)图的优美性[J].青海师范大学学报:自然科学版,2001(3).

[5] 杨显文.关于 C4m 蛇的优美性[J].工程数学学报,1995(4):108-112.

[6] 康庆德.图标号问题[J].河北师范大学学报:自然科学版,1991(1):102-105.