两类图的优美性

优美图是图论中的重要研究课题,但至今由于缺乏一般性的研究手段,寻找具有优美性的图类仍是这个领域内的研究重点.优美图也是图论中极有趣的研究课题之一,由于它的趣味性和应用性,从60年代中期一经提出,就得到了人们的重视,它在射电天文学、密码学、通讯网络编地址、电路设计、导弹控制码设计等领域有着广泛的应用.图G1n是由n个C4依次连接其对顶点而形成的一个圈.图Gp1n是将图G1n中n个连接点用n个长为1的路P替代后得到的图.图C2n是由n个C4依次连接其相邻点而形成的一个圈.图Gp2n是将图G2n中n个连接点用n个长为1的路P替代后得到的图.本文讨论了两类图Gp1n和Gp2n的优美性,用构造的方法给出了这两类图的优美标号,得出它们都是优美图的结论.

The Gracefulness of Two Classes of Graphs

The graceful graph is a very important research topic in graph theory. Because of the lack of the general researching means, searching gracefulgraphs is still a research focus in this area. The graceful graph is also one of the most interesting research subjects in graph theory. Due to its interestingness and applicability, graceful graph has gained great importance since it has been put forward in 1960s. And it has been widely applied in radio astronomy, cryptography, communication network address, circuit design, missile control code design and some other fields. Graph Gn^p1 is a graph formed by n C4 which link each other with opposite vertex to form a circle. Graph Gn^p1 is another graph formed by n C4 which link each other with path P whose length is 1 instead of linking each other with opposite vertex as in graph Gin. Graph Gn^2 is a graph formed by n C4 which link each other with adjacent vertex to form a circle. Graph Gn^p2 is another graph formed by n C4 which link each other with path P whose length is 1 instead of linking two classes of graphs of Gn^p1 and Gn^p2 each other with adjacent vertex as in graph Gn^1. We discuss the gracefulness of , give the graceful labelings of these graphs and prove its gracefulness.