张政，胡红亮

（西安航空学院理学院，陕西西安710077）

图ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的优美性

张政，胡红亮

（西安航空学院理学院，陕西西安710077）

给出了ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的定义，讨论了ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的优美性，用构造性的方法给出了一些特殊的ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的优美标号。证明了一些特殊的ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠是交错图。

圈；冠；优美图；交错图

1 引言与概念

优美图是图论中极有趣的研究课题，有着较好的应用价值和广阔的研究前景。它的研究是从1963年GRingel提出的一个猜想和1966年A Rosa的一篇论文开始的。1972年，SW Golomb明确给出了优美图的定义。近几十年，国内外获得不少关于优美图的研究成果，它们被应用于射电天文学，X-射线衍射晶体学，密码设计，通信网络编址，导弹控制码设计，同步机码设计等领域。

文中所讨论的图均为无向简单图，V(G)和E(G)分别表示图G的顶点集和边集，未说明的符号及术语均见文［1］。

定义1［1］对于一个简单图G=V(G),E(G)=(V,E)，如果对每一个顶点v∈V，存在一个非负整数θ(v)（称为顶点v的标号）使满足：

①∀u,v∈V，若u≠v，则θ(u)≠θ(v)。②max{θ(v)|v∈V}=|E|。③∀e1,e2∈E，若e1≠e2，则θ'(e1)≠θ'(e2)。其中：θ'(e)=|θ(u)-θ(v)|，e=uv（称θ'(e)为边e的标号），则G称为优美图，θ(v)称为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)-冠，简记为G(r1,r2,...,rn)。特别地，当r1=r2=...=rn=r时，称为图G的r-冠。图G的0-冠就是图G。

定义4［1］由圈Cm和Cn恰有一个公共点所组成的图记为图ωm,n。

定义5［2］G是一个优美二部图，其优美标号为θ，V(G)划分成两个集合X,Y，如果maxθ(v)＜minθ(v)，则称θ是G的交错标号，称G是在交错标号θ下的交错图。

文献［1］中证明了P1∨Pn及其r-冠是优美的，从而猜测：任意优美图的r-冠都是优美的，在此猜想的指导下，文献［3-5］中证明了：当n≡0,3(mod4)时，图Cn及其r-冠是优美图；……