图c_n及其r_冠的新的优美标号

《图c_n及其r_冠的新的优美标号》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2010年6月纯粹数学与应用数学Jun.2010第26卷第3期PureandAppliedMathematicsVol.26No.3图Cn及其r-冠的新的优美标号胡红亮(西安航空技术高等专科学校基础部,陕西西安710077)摘要：研究了关于图的r-冠的优美标号的一个问题,证明了：当n´0;3(mod4)时,图Cn及其r-冠是优美图,所给出的新的优美标号不同于现有文献中得到的结果.进而证明了当n´0(mod4)时,图Cn及其r-冠也是交错图.关键词：优美图;优美标号;r-冠;交错图中图分类号：O157.5文献标识码：A文章编号：1008-5513

2、(2010)03-0454-041引引引言言言优美图是图论中极为有趣的重要研究课题之一,有着较好的应用价值和广阔的研究前景.最近十几年来,国内外获得不少关于优美图的研究成果[1],它们被应用于射电天文学、X-射线衍射晶体学、密码设计、导弹控制码设计、同步机设计等领域[1;2].1972年Golomb明确给出了优美图的概念[3],但由于缺乏一个系统和有力的工具,迄今只能对一些特殊的图研究其优美性。马克杰等在文献[2]中证明了P1_Pn及其r-冠是优美的,从而猜测:任意优美图的r-冠都是优美的,在此猜想的指导下,曾朝英和武建春在文献[4]中证明了：

3、当n´0;3(mod4)时,图Cn及其r-冠是优美图.本文也证明了相同的结果,但是所给出的优美标号不同于文献[4]得到的结果.同时本文证明了当n´0(mod4)时,图Cn及其r-冠是也是交错图.定定定义义义1.1[2]对于一个简单图G=(V(G);E(G))=(V;E),如果对每一个顶点v2V,存在一个非负整数µ(v)(称为顶点v的标号)使满足:(1)8u;v2V,若u6=v,则µ(u)6=µ(v);(2)maxfµ(v)jv2Vg=jEj;(3)8e1;e22E,若e16=e2,则µ0(e1)6=µ0(e2).其中µ0(e)=jµ(u)¡µ(

4、v)j,e=uv(称µ0(e)为边e的标号),则G称为优美图,µ(v)称为G的一个优美标号.定定定义义义1.2[4]在一个图的每个顶点上粘上一个含有r个悬挂点的星T,称此图为r-冠.r+1定定定义义义1.3[5]设G是一个有n个顶点的优美二分图,其优美标号为µ(v),V(G)分成两个集合X和Y,如果有maxµ(v)

5、结论论论及及及证证证明明明文献[4]证明了当n´0;3(mod4)时,则图Cn及其r-冠是优美图,其优美标号详见文献[4].下面给出图Cn及其r-冠的一个新的优美标号(如图1),这不同于文献[4]的结果.定定定理理理2.1当n´0;3(mod4)时,则图Cn及其r-冠是优美图.当n´0(mod4)时,则图Cn及其r-冠也是交错图.证证证明明明设图Cn上的顶点依次为x1;x2;¢¢¢;xn.设原优美图Cn(n´0;3(mod4))的优美标号为µ(xi),图Cn的r-冠的标号为µ¤(xi).如图1标出其顶点顺序.x1x1x2xnx2xnx3xn−1

6、x3xn−1೒Cn೒Cnⱘr−图1优美标号(1)当n´0(mod4)时,可以验证图Cn的下面标号µ(xi)为图Cn的一个优美标号.8>>µ(x2k)=n¡k+1;k=1;2;¢¢¢;n=4,<µ(x2k)=n¡k;k=n=4+1;n=4+2;¢¢¢;n=2,>>:µ(x2k¡1)=k¡1;k=1;2;¢¢¢;n=2.(2)当n´0(mod4)时,定义图Cn的r-冠的顶点标号µ¤(xi)为:对Cn中的点标以:8µ¤(x)=(r+1)µ(x)¡r;k=1;2;¢¢¢;n=4,>>2k2k<µ¤(x)=(r+1)µ(x);k=n=4+1;n=4+2;

7、¢¢¢;n=2,2k2k>>:¤µ(x2k¡1)=µ(x2k¡1)+r(k¡1);k=1;2;¢¢¢;n=2.与x1相邻的r个悬挂点分别标以：n(r+1);n(r+1)¡1;¢¢¢;n(r+1)¡r+1;当k6=0时,与x2k+1相邻的r个悬挂点分别标以:µ¤(x2k)¡1;µ¤(x2k)¡2;¢¢¢;µ¤(x2k)¡r;k=1;2;¢¢¢;n=4¡1;n=4+1;n=4+2;¢¢¢;n=2¡1;µ¤(x2k)¡2;µ¤(x2k)¡3;¢¢¢;µ¤(x2k)¡r¡1;其中k=n=4;与x2k相邻的r个悬挂点分别标以：µ¤(x2k¡1)+1;µ¤

8、(x2k¡1)+2;¢¢¢;µ¤(x2k¡1)+r.可以验证以上标号µ¤(xi)为图Cn的r-冠的一个优美标号.(3)当n´3(mod4)时,可以验证