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

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

Рассмотрены базовые теоретические сведения по Фибоначчи-грациозным графам. Под Фибоначчи-грациозной разметкой графа 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...

Full description

Saved in:
Bibliographic Details
Date:2020
Main Author: Semeniuta, Marina
Format: Article
Language:Russian
Published: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020
Subjects:
Фібоначчі-граціозна розмітка
супер-Фібоначчі-граціозна розмітка
цикл
ейлерів граф
одноточкове з’єднання графів
Online Access:https://jais.net.ua/index.php/files/article/view/51
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Problems of Control and Informatics

Institution

Problems of Control and Informatics
id oai:ojs2.jais.net.ua:article-51
record_format ojs
institution Problems of Control and Informatics
baseUrl_str
datestamp_date 2024-03-14T11:05:53Z
collection OJS
language Russian
topic Фібоначчі-граціозна розмітка
супер-Фібоначчі-граціозна розмітка
цикл
ейлерів граф
одноточкове з’єднання графів
spellingShingle Фібоначчі-граціозна розмітка
супер-Фібоначчі-граціозна розмітка
цикл
ейлерів граф
одноточкове з’єднання графів
Semeniuta, Marina
Фібоначчі- та супер-Фібоначчі-граціозні розмітки деяких видів графів
topic_facet Fibonacci graceful labelling
super Fibonacci graceful labelling
cycle
Eulerian graph
one-point union of graphs
Фібоначчі-граціозна розмітка
супер-Фібоначчі-граціозна розмітка
цикл
ейлерів граф
одноточкове з’єднання графів
Фибоначчи-грациозная разметка и супер-Фибоначчи-грациозная разметка
цикл,
эйлеров граф
одноточечное соединение графов
format Article
author Semeniuta, Marina
author_facet Semeniuta, Marina
author_sort Semeniuta, Marina
title Фібоначчі- та супер-Фібоначчі-граціозні розмітки деяких видів графів
title_short Фібоначчі- та супер-Фібоначчі-граціозні розмітки деяких видів графів
title_full Фібоначчі- та супер-Фібоначчі-граціозні розмітки деяких видів графів
title_fullStr Фібоначчі- та супер-Фібоначчі-граціозні розмітки деяких видів графів
title_full_unstemmed Фібоначчі- та супер-Фібоначчі-граціозні розмітки деяких видів графів
title_sort фібоначчі- та супер-фібоначчі-граціозні розмітки деяких видів графів
title_alt Фибоначчи- и супер-фибоначчи-грациозные разметки некоторых видов графов
Fibonacci and super Fibonacci graceful labellings of some types of graphs
description Рассмотрены базовые теоретические сведения по Фибоначчи-грациозным графам. Под Фибоначчи-грациозной разметкой графа 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.
publisher V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
publishDate 2020
url https://jais.net.ua/index.php/files/article/view/51
work_keys_str_mv AT semeniutamarina fibonaččiisuperfibonaččigracioznyerazmetkinekotoryhvidovgrafov
AT semeniutamarina fíbonaččítasuperfíbonaččígracíoznírozmítkideâkihvidívgrafív
AT semeniutamarina fibonacciandsuperfibonaccigracefullabellingsofsometypesofgraphs
first_indexed 2025-10-30T02:48:33Z
last_indexed 2025-10-30T02:48:33Z
_version_ 1847373346572861440
spelling oai:ojs2.jais.net.ua:article-512024-03-14T11:05:53Z Фибоначчи- и супер-фибоначчи-грациозные разметки некоторых видов графов Фібоначчі- та супер-Фібоначчі-граціозні розмітки деяких видів графів Fibonacci and super Fibonacci graceful labellings of some types of graphs Semeniuta, Marina Fibonacci graceful labelling super Fibonacci graceful labelling cycle Eulerian graph one-point union of graphs Фібоначчі-граціозна розмітка супер-Фібоначчі-граціозна розмітка цикл ейлерів граф одноточкове з’єднання графів Фибоначчи-грациозная разметка и супер-Фибоначчи-грациозная разметка цикл, эйлеров граф одноточечное соединение графов Рассмотрены базовые теоретические сведения по Фибоначчи-грациозным графам. Под Фибоначчи-грациозной разметкой графа 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. Розглянуто базові теоретичні відомості щодо Фібоначчі-граціозних графів. Під Фібоначчі-граціозною розміткою графа 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. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020-07-22 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/51 10.34229/1028-0979-2021-1-10 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 66 № 1 (2021): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 105-121 International Scientific Technical Journal "Problems of Control and Informatics; Том 66 № 1 (2021): International Scientific Technical Journal "Problems of Control and Informatics"; 105-121 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 66 No. 1 (2021): International Scientific Technical Journal "Problems of Control and Informatics"; 105-121 2786-6505 2786-6491 10.34229/1028-0979-2021-1 ru https://jais.net.ua/index.php/files/article/view/51/68 Copyright (c) 2020 Marina Semeniuta https://creativecommons.org/licenses/by-nc-nd/4.0/

Similar Items