КОРОТКИЙ ОГЛЯД МЕТОДІВ ПОБУДОВИ ГРАЦІЙНОЇ РОЗМІТКИ ГРАФІВ

З. О. Шерман

З. О. Шерман Інститут кібернетики ім. В.М. Глушкова НАН України

Ключові слова: граційна розмітка, метод перенесення гілок і ребер, метод Δ-побудови, цілочисельне програмування, цикли з хордами

Анотація

У наведеній роботі запропоновано огляд методів граційної розмітки дерев, а також інших класів графів з метою їх систематизації. Виділені приватні конструктивні методи для дерев. Детально описаний один з універсальних методів знаходження граційної розмітки графів, що має за основу алгоритми лінійного цілочисельного програмування. Розглянуті методи з аналітичним підходом для графів, породжених циклами.

Посилання

1. Ringel G. Problem 25 / G. Ringel // In Theory of Graphs and Its Applications. Proceeding of the Symposium held in Smolenice in June 1963. Publishing House of the Czech. Acad. of Science. Prague. – 1964. – P. 162.
2. Rosa A. On certain valuations of the vertices of a graph / A. Rosa // Theory of Graphs. International Symposium, Rome, July. – 1966. – Gordon and Breach, New York and Dunod Paris. – 1967. – P. 349-355.
3. Bermond J. Graceful graphs, radio antennae and French windmills / J. Bermond // Graph Theory and Combinatorics. – 1979. – P. 18-37.
4. Hrnciar P. All trees of diameter five are graceful / P. Hrnciar, A. Haviar // Discrete Mathematics. – 2001. – № 233 – P. 133-150.
5. Hrnciar P. A new family of graceful trees / P. Hrnciar, G. Monoszova // preprint. Combinatorica o.p.s. Department of Applied Mathematics. VfB – Technical University Ostrava, 2007.
6. Cahit I. Are all complete binary trees graceful? / I. Cahit // American Mathematical Monthly. – 1976. – Vol. 83. – P. 35-37.
7. Stanton R. Labeling of balanced trees / R. Stanton, C. Zarnke // Proc. 4th Southeast Conf. Combin. Graph Theory, Computing. – 1973. – P. 479-495.
8. Koh K. M. On graceful trees / K. M. Koh, D. G. Rogers, T. Tan // Nanta Mathematics. – 1977. – Vol. 10, № 2. – P. 207-211.
9. Koh K. M. Two theorems on graceful trees / K. M. Koh, D. G. Rogers, T. Tan // Discrete Mathematics. – 1979. – Vol. 25. – P. 141-148.
10. Koh K. M. Products of graceful trees / K. M. Koh, D. G. Rogers, T. Tan // Discrete Mathematic. – 1980. – Vol. 31. – P. 279-292.
11. Burzio M. The Subdivision Graph of a Graceful Tree is a Graceful Tree / M. Burzio, G. Ferrarese // Discrete Mathematics. – 1998. – Vol. 181, № 1-3. – P. 275-281.
12. Redl T. A. Graceful graphs and graceful labelings: two mathematical programming formulations and some other new results / T. A. Redl // Tech. Report TR03-01, CAAM Department, Rice University. – Texas, 2003.
13. Eshghi K. Applications of mathematical programming in graceful labeling of graphs / K. Eshghi, P. Azimi // Journal of Applied Mathematics. – 2004. – Vol. 1. – P. 1-8.
14. Eshghi K. An algorithm for finding a feasible solution of graph labeling problems / K. Eshghi, P. Azimi // Utilitas Мathematica. – 2007. – Vol. 72. – P. 163-174.
15. Ma K. J. About the Bodendiek’s conjecture of graceful graph / K. J. Ma, C. J. Feng // Journal. Mathematical Research and Exposition. – 1984. – Vol. 4. – P. 15-18.
16. Kaneria V. J. Some graceful graphs / V. J. Kaneria, H. M. Makadia, M. Meghapara // International Journal of Mathematics and Soft Computing. – 2014. – Vol. 4, № 2. – P. 165-172.
17. Sethuraman G. Gracefulness of a cycle with parallel Pk-chords / G. Sethuraman, A. Elumalai // Australasian Journal of Combinatorics. – 2005. – Vol. 32. – P. 2005-2011.
18. Sekar C. Studies in Graph Theory / C. Sekar // Ph.D. Thesis. Madurai Kamaraj University. – 2002.
19. Vaidya S. K. Some new graceful graphs / S. K. Vaidya, L. Bijukumar // International Journal of Mathematics and Soft Computing. – 2011. – Vol. 1, № 1. – P. 37-45.