A BRIEF REVIEW OF GRACEFUL GRAPHS CONSTRUCTION METHODS - Sherman, Z. O. (Computer Science and Applied Mathematics, 2016)
The paper presents a brief review of methods for constructing graceful labeling of trees, as well as other classes of graphs for their systematization. For trees among the most famous and used methods those that are developing and have not lost their relevance are highlighted. They are method of transfering branches, edges and Δ-construction method. Section 3 describes in detail one of the universal methods of finding a graceful labeling of small orders graphs. The basis of this method is in linear integer programming algorithms. Special attention in this paper is given to publications which deal with graphs generated by cycles. They all have a general similarity – analytical approach in labeling construction. Section 2 analyzes methods of graceful graphs construction in the order of their occurrence. The constructive method of graceful trees constructtion presented by P. Hrnciar and A. Haviar is distinguished. The authors proposed to transfer a certain amount of end-edges and subtrees emanating from one vertex of the graceful tree to another vertex of it. They proved that all the trees of diameter 4 and some trees of diameter 5 are graceful. Further development of transferring methods was done by M. Superdock in 2014, who suggested the use of certain sequences of transfering end-edges to construct some classes of graceful trees of diameter 6. Section 3.2 deals with a particular constructive approach of defining graceful trees of large size among known graceful trees. K. Koh, D. Rogers, T.Tan completed the construction of the new graph, adding to the disjoint union of isomorphic copies of this graceful graph T, the additional vertice connected by edges with the isomorphic image of a vertex T. The method is used for the gracefulness study of symmetrical trees. The same authors summarized this method, identifying isomorphic images of the vertices of T with an additional vertex, as well. In 1979, the construction of graceful tree was implemented by a given pair of graceful trees and was called Δ-construction. Using it, K. Koh and others have proved gracefulness of the full m-ary tree. In 1998 M. Burzio, G. Ferrarese made additions to the algorithm of Δ-construction and called it его Δ+1-construction. Using the method of Δ+1-construction the subdivision graph gracefulness was proved. Section 4 describes a universal method of graceful label constructing for different classes of graphs. In 2003 T. Redl based algorithm for finding the graceful labeling of Petersen graphs and double cones on one of the methods of linear integer programming. Similar results were obtained in K. Eshghi and P. Azimi’s studies. The disadvantages of this method are related to the limited size of the graphs. Section 5 distinguishes the graceful labeling methods for constructing graphs with a cyclic structure. The basis of some of them is in the findings of a certain functional dependence, and that of the others is in a recursive method. A. Rosa having considered gracefulness of cycle Сn was the founder of this direction. In 1977 R. Bodendiek, H. Schumacher and H. Wagner first studied the cycles with a chord and constructed graceful labeling for some special cases of such cycles. Their research was summarized by C. Delorne, M. Maheo, K. Koh, H. Tan in 1980 and K. Ma and C. Feng in 1984 who proved that any cycle with chord is graceful. In 1985 K. Koh and others offered a method of graceful labeling construction for cycles with Pk-chords for k=3 and hypothesized that all cycles with Pk-chords are graceful. In 2005 G.Sethuraman and A.Elumalai presented a recursive method of constructing graceful labelings for cycles Сn (n≥6) with parallel Pk-chords, with k=3, 4, 6, 8, 10, and suggested that the cycles Сn with parallel Pk-chords were graceful for any even k. In 2013 G.Sethuraman A.Elumalai studied methods of constructing graceful Сn (n≥8) cycles with zigzag chords, which link the alternating tops of the cycle. In 2014 Kaneria V.J., Makadia H.M. and Meghapara M. studied the cycles with double chords. They provided a method of constructing graceful labeling for any cycle Сn with a double chord where n≡2(mod 4).