齿轮图冠的优美性

The Gracefulness of the Coronal of Gear Wheels

图的优美性是图的一个重要性质,有着广泛的应用.优美图是图论中极有趣的研究课题之一.马克杰和冯成进已经证明了:所有的齿轮图都是优美图.研究图的优美性其实就是寻找图的优美标号.已经证明判定任意一个图是否为优美图是一个NP-困难问题,即对于给定的一个图,判定它是否为优美图,不存在一个有效算法.在论文中,我们利用构造的方法,具体找出任一齿轮图的冠的一个优美标号,从而证明了所有齿轮图的冠是优美图.

The gracefulness of graphs is an important quality,having widespread application.Graceful graph is one of the most interesting research topics in graph theory.Ma kejie and Feng chengjin testified that every gear wheel is graceful.The study on the gracefulness of graph is,in fact,to find a graceful labeling of a graph.It has been proved that it is a NP-difficult problem to determine whether a graph is a graceful graph,that is,to determine whether a given graph is a graceful graph or not,and there is not an effective algorithm for the question.We make use of construction method to find out a graceful labeling of the crown of any gear graph,which proves that the crown of all gear graphs are graceful graphs.