Фибоначчи и супер-Фибоначчи-грациозные разметки некоторых видов графов

Abstract

Розглянуто базові теоретичні відомості щодо Фібоначчі-граціозних графів. Під Фібоначчі-граціозною розміткою графа G=(V,E) розміру q розуміють ін’єктивну функцію f:V→{0,1,2,3,4,…,Fq} яка індукує бієктивну функцію f*:E→{F1, F2,F3,…,Fq} де F1=1, F2=1, F3=2, Fq= Fq-2+Fq-1 за правилом f*(uv)=|f(u)-f(v)| для будь-яких суміжних вершин u,v ϵ V. Граф, що допускає таку розмітку, називається Фібоначчі-граціозним. У даній роботі введено поняття супер-Фібоначчі-граціозної розмітки звуженням множини вершинних міток, тобто f:V→{F0,F1,F2,…,Fq}. Виділено чотири типи задач, що підлягають дослідженню. У задачі першого типу піднімається наступне питання: чи існує граф, що допускає певний вид розмітки, і за яких умов це має місце? Задача другого типу — це задача побудови: при заданій системі вимог для графа необхідно побудувати (хоча б одну) його розмітку, яка задовольняла б цій системі. Наступні два типи задач відносяться до задач переліку: для заданого графа визначити число різних Фібоначчі- і/або супер- Фібоначчі-граціозних розміток; побудувати всі різні розмітки заданого виду. В результаті вирішення цих задач знайдено функції, які породжують Фібоначчі- і супер-Фібоначчі-граціозні розмітки для графів циклічної структури; отримано необхідні і достатні умови існування Фібоначчі-граціозної розмітки дизʼюнктивного обʼєднання циклів, супер-Фібоначчі-граціозної розмітки циклів, ейлерових графів; визначено число нееквівалентних розміток циклу; представлено умови існування супер-Фібоначчі-граціозної розмітки одноточкового зʼєднання довільних зв’язних супер-Фібоначчі-граціозних графів G1,G2,…,Gk.

We consider the basic theoretical information regarding the Fibonacci graceful graphs. An injective function V→{0,1,2,3,4,…,Fq} is said a Fibonacci graceful labelling of a graph G=(V,E) of a size , if it induces a bijective function f*:E→{F1, F2,F3,…,Fq}on the set of edges , where F1=1, F2=1, F3=2, Fq= Fq-2+Fq-1, by the rule f*(uv)=|f(u)-f(v)|, for any adjacent vertices u,v ϵ V. A graph that allows such labelling is called Fibonacci graceful. In this paper, we introduce the concept of super Fibonacci graceful labelling, narrowing the set of vertex labels, i.e. f:V→{F0,F1,F2,…,Fq} Four types of problems to be studied are selected. In the problem of the first type, the following question is raised: is there a graph that allows a certain kind of labelling, and under what conditions does this take place? The problem of the second type is the problem of construction: it is necessary, for a given system of requirements for the graph, to construct (at least one) its labelling that would satisfy this system. The following two types of problems relate to enumeration problems: for a given graph, determine the number of different Fibonacci and / or super Fibonacci graceful labellings; build all the different labellings of a given kind. As a result of solving these problems, functions were found that generate Fibonacci and super Fibonacci graceful labellings for graphs of cyclic structure; necessary and sufficient conditions for the existence of Fibonacci graceful labelling for disjunctive union of cycles, super Fibonacci graceful labelling for cycles, Eulerian graphs are obtained; the number of non-equivalent labellings of the cycle is determined; conditions for the existence of a super Fibonacci graceful labelling of a one-point connection of arbitrary connected super Fibonacci graceful graphs G1,G2,…,Gk are presented.