ФІБОНАЧЧІ- ТА СУПЕР-ФІБОНАЧЧІ-ГРАЦІОЗНІ РОЗМІТКИ ДЕЯКИХ ВИДІВ ГРАФІВ

УДК 519.1

Volume 66, Issue 1, 2021, pages 105-121

DOI: https://doi.org/10.34229/0572-2691-2021-1-10

Завантажити статтю 

Семенюта Марина Фролівнакандидат фізико-математичних наук, доцент, зав. кафедрою Льотної академії Національного авіаційного університету, Кропивницький


Abstract

Розглянуто базові теоретичні відомості щодо Фібоначчі-граціозних графів. Під Фібоначчі-граціозною розміткою графа розміру розуміють ін’єктивну функцію яка індукує бієктивну функцію де за правилом для будь-яких суміжних вершин Граф, що допускає таку розмітку, називається Фібоначчі-граціозним. У даній роботі введено поняття супер-Фібоначчі-граціозної розмітки звуженням множини вершинних міток, тобто . Виділено чотири типи задач, що підлягають дослідженню. У задачі першого типу піднімається наступне питання: чи існує граф, що допускає певний вид розмітки, і за яких умов це має місце? Задача другого типу — це задача побудови: при заданій системі вимог для графа необхідно побудувати (хоча б одну) його розмітку, яка задовольняла б цій системі. Наступні два типи задач відносяться до задач переліку: для заданого графа визначити число різних Фібоначчі- і/або супер- Фібоначчі-граціозних розміток; побудувати всі різні розмітки заданого виду. В результаті вирішення цих задач знайдено функції, які породжують Фібоначчі- і супер-Фібоначчі-граціозні розмітки для графів циклічної структури; отримано необхідні і достатні умови існування Фібоначчі-граціозної розмітки дизʼюнк­тивного обʼєднання циклів, супер-Фібоначчі-граціозної розмітки циклів, ейлерових графів; визначено число нееквівалентних розміток циклу; представлено умови існування супер-Фібоначчі-граціозної розмітки одноточкового зʼєднання довільних зв’язних супер-Фібоначчі-граціозних графів … …, .


REFERENCES

  1. Gallian J.A. A dynamic survey of graph labeling. The Electronic Journal of Combinatorics. 2019. DS6: Dec 15. 535 p. DOI: https://doi.org/10.37236/27
  2. Stakhov A.P. Fibonacci matrices, a generalization of the Cassini formula and a new coding theory. Chaos, Solitons & Fractals. 2006. 30, N 1. P. 56–66. DOI: https://doi.org/10.1016/j.chaos.­2005.12.054
  3. Prajapat S., Jain A., Thakur R.S. A novel approach for information security with automatic variable key using Fibonacci Q-matrix. International Journal of Computer & Communication Technology. 2012. 3, N 3. P. 54–57.
  4. Tas N., Ucar S., Ozgur N.Y., Kaymak O.O. A new coding/decoding algorithm using Fibonacci numbers. Discrete Mathematics, Algorithms and Applications. 2018. 10, N 2. P. 1–10. DOI: https://doi.org/10.1142/S1793830918500271.
  5. Hsu W.-J. Fibonacci cubes — a new interconnection technology. IEEE Transactions on Parallel and Distributed Systems. 1993. 4, N 1. P. 3–12.
  6. Liu J., Hsu W.-J., Chung M.J. Generalized Fibonacci cubes are mostly Hamiltonian. Journal of Graph Theory. 1994. 18. P. 817–829.
  7. Bresar B., Klavzar S. Θ-graceful labelings of partial cubes. Discrete Mathematics. 2006. 306, N 13. P. 1264–1271. DOI: https://doi.org/10.1016/j.disc.2006.02.013.
  8. Horibe Y. Notes on Fibonacci trees and their optimality. Fibonacci Quarterly. 1983. 21, N 2. P. 118–28.
  9. Koh K.M., Lee D.G., Tan T. Fibonacci trees. SEA bull. math. 1978. 2, N 1. P. 45–47.
  10. Bange D.W., Barkauskas A.E. Fibonacci graceful graphs. Fibonacci quarterly. 1983. 21, N 3. P. 174–188.
  11. Kathiresan K.M., Amutha S. Fibonacci graceful graphs. Ars Combinatoria. 2010. 97. P. 41–50.
  12. Vaidya S.K, Prajapati U.M. Fibonacci and super Fibonacci graceful labeling of some cycle related graphs. International Journal of Mathematical Combinatorics. 2011. 4. P. 56–69.
  13. Sridevi R., Navaneethakrishnan S., Nagarajan K. Super Fibonacci graceful labeling. International Journal of Mathematical Combinatorics. 2010. 3. P. 22–40.
  14. Шерман З. Некоторые результаты по Фибоначчи грациозным разметкам графов. Теорія оптимальних рішень. 2015. С. 35–40.
  15. Chartrand G., Lesniak L., Zhang P. Graphs and Digraphs. 6th ed. CRC Press, Taylor & Francis Group. Textbooks in mathematics, 2015. 640 p.