关于圈C4h的（r1，r2，…，r4h）-冠的优美性

吴跃生

（华东交通大学基础科学学院，江西南昌330013）

本文所讨论的图均为无向简单图，V(G)和E(G)分别表示图G的顶点集和边集。

定义1[1]对于一个图G=(V，E)如果存在一个单射，使得对所有边e=(u，v) ∈E(G)，由导出的是一个双射，则称G是优美图，θ是G的一组优美标号，称θ′为G的边上的由θ导出的诱导值。

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

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

定义4[2]G是一个优美二部图，其优美标号为θ，V(G)划分成两个集合X，Y，如果mv∈aXxθ(v)＜mv∈iYnθ(v)，则称θ是G的交错标号。称G是在交错标号θ下的交错图。

事实上，G是在交错标号θ下的交错图就是文[1]中所定义的平衡图。

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

文献[3-6]在上猜想的引导下，证明了一些优美图（如圈Cn((n≡0)，3(m od4 ))）的r-冠是优美的。

文献[7]给出了圈Cn的(r1，r2，…，rn)-冠的定义，讨论了当n=7，8 时，圈Cn的 (r1，r2，…，rn)-冠的优美性。本文讨论了当n=4h时，圈Cn的(r1，r2，…，rn)-冠的优美性。

1 主要结果及其证明

定理 当n=4h，h为非零自然数，ri为任意自然数（i=1，2，…，4h），圈Cn的(r1，r2，…，rn)-冠的顶点集如图1所示，V(Cn)=(v1，v2，…，vn)，与vi邻接的端点（或叶）记为xij(vi∈V(Cn)，j=1，2，…，ri)，当时，圈Cn的 (r1，r2，…，rn)-冠是交错图。

证明 当n=4h，h≤1时，下面用构造性的方法给出圈Cn的(r1，r2，…，rn)-冠的两种交错（平衡）标号。第一种交错（平衡）标号。定义圈Cn的(r1，r2，…，rn)-冠的顶点标号θ为

因此θ是C4h的(r1，r2，…，r4h)-冠的优美标号。即C4h的 (r1，r2，…，r4h)-冠是优美图。

令:

因此θ是C4h的(r1，r2，…，r4h)-冠的交错标号。即C4h的 (r1，r2，…，r4h)-冠是交错图。

第二种交错（平衡）标号。下面定义圈Cn的(r1，r2，…，rn)-冠的另一种标号交错（平衡）θ1为:（设θ是C4h的(r1，r2，…，r4h)-冠的第一种交错标号）

证明类似第一种优美标号，此处略。

在定理中，令r1=r2=…=r4h=r，有

推论1C4h的r-冠是交错图。

引理[1]交错图至少有4种不同的交错标号（即标号为θ的交错图可以派生出另外3种不同的交错标号）。

推论2 当n=4h，h为非零自然数，ri为任意自然数（i=1，2，…，4h），当时，圈Cn的

(r1，r2，…，rn)-冠至少有8种不同的交错标号。

例 下面根据定理给出圈C12的(2 ，2，0，4，0，1，0，0，2，0，5，0)-冠的两种交错标号，如图2，图3所示。

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

[2]杨显文，张志尚.一类交错图并的优美性[J].吉林工程技术师范学院学报:自然科学版，2007，23（6）:8-10.

[3]武建春.图D2，4k与它的r-冠的优美性[J].内蒙古电大学刊，2002（1）:34.

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

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

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

[7]吴跃生，李咏秋.关于圈Cn的（r1，r2，…，rn）-冠（n=7，8）的优美性[J].阜阳师范学院学报:自然科学版，2010，27（3）:20-23.