УДК 519.1
Volume 66, Issue 1, 2021, pages 105-121
DOI: https://doi.org/10.34229/0572-2691-2021-1-10
Семенюта Марина Фролівна, кандидат фізико-математичних наук, доцент, зав. кафедрою Льотної академії Національного авіаційного університету, Кропивницький
Abstract
Розглянуто базові теоретичні відомості щодо Фібоначчі-граціозних графів. Під Фібоначчі-граціозною розміткою графа розміру розуміють ін’єктивну функцію яка індукує бієктивну функцію де за правилом для будь-яких суміжних вершин Граф, що допускає таку розмітку, називається Фібоначчі-граціозним. У даній роботі введено поняття супер-Фібоначчі-граціозної розмітки звуженням множини вершинних міток, тобто . Виділено чотири типи задач, що підлягають дослідженню. У задачі першого типу піднімається наступне питання: чи існує граф, що допускає певний вид розмітки, і за яких умов це має місце? Задача другого типу — це задача побудови: при заданій системі вимог для графа необхідно побудувати (хоча б одну) його розмітку, яка задовольняла б цій системі. Наступні два типи задач відносяться до задач переліку: для заданого графа визначити число різних Фібоначчі- і/або супер- Фібоначчі-граціозних розміток; побудувати всі різні розмітки заданого виду. В результаті вирішення цих задач знайдено функції, які породжують Фібоначчі- і супер-Фібоначчі-граціозні розмітки для графів циклічної структури; отримано необхідні і достатні умови існування Фібоначчі-граціозної розмітки дизʼюнктивного обʼєднання циклів, супер-Фібоначчі-граціозної розмітки циклів, ейлерових графів; визначено число нееквівалентних розміток циклу; представлено умови існування супер-Фібоначчі-граціозної розмітки одноточкового зʼєднання довільних зв’язних супер-Фібоначчі-граціозних графів … …, .
REFERENCES
- 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
- 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
- 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.
- 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.
- Hsu W.-J. Fibonacci cubes — a new interconnection technology. IEEE Transactions on Parallel and Distributed Systems. 1993. 4, N 1. P. 3–12.
- Liu J., Hsu W.-J., Chung M.J. Generalized Fibonacci cubes are mostly Hamiltonian. Journal of Graph Theory. 1994. 18. P. 817–829.
- 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.
- Horibe Y. Notes on Fibonacci trees and their optimality. Fibonacci Quarterly. 1983. 21, N 2. P. 118–28.
- Koh K.M., Lee D.G., Tan T. Fibonacci trees. SEA bull. math. 1978. 2, N 1. P. 45–47.
- Bange D.W., Barkauskas A.E. Fibonacci graceful graphs. Fibonacci quarterly. 1983. 21, N 3. P. 174–188.
- Kathiresan K.M., Amutha S. Fibonacci graceful graphs. Ars Combinatoria. 2010. 97. P. 41–50.
- 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.
- Sridevi R., Navaneethakrishnan S., Nagarajan K. Super Fibonacci graceful labeling. International Journal of Mathematical Combinatorics. 2010. 3. P. 22–40.
- Шерман З. Некоторые результаты по Фибоначчи грациозным разметкам графов. Теорія оптимальних рішень. 2015. С. 35–40.
- Chartrand G., Lesniak L., Zhang P. Graphs and Digraphs. 6th ed. CRC Press, Taylor & Francis Group. Textbooks in mathematics, 2015. 640 p.