Qn的优美性与协调性

nQ 的优美性与协调性 （河北交通职业技术学院） 李国竹 摘要：本文证明了王冠 nQ 的优美性与协调性。 关键词：王冠 nQ ，优美标号，优美图，协调标号，协调图。 中图分类号：O157.5。 The gracefulness and harmoniousness of crownes nQ （Hebei Communications Vocational and Technical college） Li guo zhu Abstract:The paper proves the gracefulness and harmoniousness of crownes nQ . Key s:, crownes nQ ,graceful labling, graceful graph., felicitous labeling, felicitous graph. 1972 年 S.W.Golomb 给出了优美图的确切定义 ]3[ ，设简单图 G=（V，E）的边数是|E|=m， 若存在从 V到{0，1，2，…，m}的单射 f，使得导出映射 g(uv)=|f(u)-f(v)| , uv∈E 是从 E 到{1，2，…，m}的双映射, 则称 f是图 G 的优美标号（graceful labeling），图 G 叫做优美 图（graceful graph）。协调性的概念见文献[1]，设简单图 G（V,E）的边数│E│=q，如果存 在单映射 f(v):V→ {0,1,2,…,q-1},使得导出映射 G(uv)= │f(x)+f(y)│mod q 是从 E 到 {0,1,2,…,q-1}的双映射，那么称 f(v)是简单图 G（V,E）的协调标号(felicitous labeling)， 称简单图 G（V,E）为具有协调性的协调图(felicitous graph)。世界各地的工作者对图的 优美性与协调性进行了广泛的研究。许多数学家给出了许多具有应用价值的研究结论，并且 提出了很多至今未被论证的猜想。1979 年，R.Frucht 证明了“所有的王冠 nQ 都是优美的” ]2[ 。 1983 年，T.Gracel 提出猜想“所有的王冠 nQ 都是协调的” ]4[ ，王冠是指在回路（圈）Cn 的每个顶点上都增加一条悬挂边所组成的图，记作 nQ 。本文作者证明了这个猜想。 命题 1 所有的王冠 nQ 都是优美的。 证明 由于篇幅限制，在此只写出 )(4 NkQ k  的优美标号，其它情况可以类似给出。 ix 表示回路 C4k的第个 i 顶点， iy 表示与顶点 ix 在同一条悬挂边上的顶点，i=1,2,… ,4k。             .14,...,52,32),32(26 ;2,...,4,2),2(8 ;4,...,42,22),22(12 ;12,...,3,1,1 )( kkkikik kiik kkkikik kii xf i                .14,...,52,32),32(22 ;2,...,4,2,1 ;4,...,42,22),22(16 ;12,...,5,3),3(18 ;1,4 )( kkkikik kii kkkikik kiik ik yf i 命题 2 所有的王冠 nQ 都是协调的。 Doc uCo m P DF Tria l ww w.pd fwiz ard. com 证明 由于篇幅限制，在此只写出 )(12 NkQ k  与 )(4)1(6 NkQ k  的协调标号，其它情况 可以类似给出。 1． )(12 NkQ k  的协调标号 ix 表示圈的第个 i 顶点， iy 表示与顶点 ix 在同一条悬挂边上的顶点，i=1,2,… ,2k+1。       .2,...,6,4,2),2(22 ;12,...,5,3,1,1 )( kiik kii xf i       .2,...,4,2,1 ;12,...,3,1),1(12 )( kii kiik yf i 2． )(4)1(6 NkQ k  的协调标号 ix 表示圈的第个 i 顶点， iy 表示与顶点 ix 在同一条悬挂边上的顶点，i=1,2,… ,4k+4。             .26,512 ;36,26 ;46,...,13,3,33 ;13,...,3,2,1,1 )( kik kik kkkikik kii xf i                                   .26,36 ;36,1012 ;56,...,103,73),73(19 ;66,...,93,63),63(49 ;46,...,83,53),53(39 ;43,9 ;33,23),23(49 ;3,13 ;13,13, 2 )13(329 ;23,...,3,2),2(16 ;1,712 )( kik kik kkkikik kkkikik kkkikik kik kkikik kik kkikik kiik ik yf i 2 维、3 维空间中许多空间图形，它们的优美性与协调性有待研究，空间图形的优美性 与协调性的研究情况可以参见 Joseph A. Gallian 写的《A Dynamic Survey of Graph Labeling》（The Electronic Journal of Combinatorics 14 2007 #DS6 ）。 参考文献：[1] Joseph A. Gallian 《A Dynamic Survey of Graph Labeling》， The Electronic Journal of Combinatorics 14 2007 #DS6 。 [2]R.Frucht,Graceful numbering of wheels and related graphs,Ann.N.Y.Acad.Sci.319(1979),219-229. [3]S.W.Golomb,How to number a graph,Graph theory and computing,Academic Press,New York,(1972),23-37. [4]T.Gracel,on sequential labelings of graphs,Journal of graph Theory,Vol 7(1983),195-210. [5] 马克杰.优美图[M].北京:北京大学出版社,1991. 作者简介 李国竹 高级讲师 ，研究方向是代数与组合图论。 通讯方式 0311-83016983，15512170663；河北交通职业技术学院 邮编 050091； e-mail:lgzhnet@126.com . 住址 石家庄市建国西路 661 号西二环宝曼家园 2-5-402 室；邮编 050081。 Doc uCo m P DF Tria l ww w.pd fwiz ard. com