Liczby typu Fibonacciego, ich własności i zastosowania do problemów zliczania w grafach
Loading...
Date
2021
Authors
Advisor
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Numbers of the Fibonacci type, their properties and applications to the counting problems in graphs
Abstract
W rozprawie zostały przedstawione rezultaty dotyczące ciągów typu Fibonacciego, czyli ciągów zdefiniowanych jednorodnym liniowym równaniem rekurencyjnym, ze szczególnym uwzględnieniem ich zastosowań w grafach. Wyniki zawarte w rozprawie dotyczą wyznaczania -indeksu w grafach jednocyklowych i są kontynuacją istniejących w literaturze badań tego indeksu w drzewach. Przy wykorzystaniu własności liczb Fibonacciego, Lucasa oraz liczb telefonicznych, zostały przedstawione oszacowania dolne i górne -indeksu w grafach jednocyklowych, wraz z podaniem pełnej charakteryzacji grafów ekstremalnych. Ponadto uzyskane zostały kolejne najmniejsze i największe wartości tego indeksu w grafach jednocyklowych i opisane kolejne grafy ekstremalne. Dla szczególnych klas grafów jednocyklowych -indeks został wyznaczony dokładnie, co z kolei spowodowało uzyskanie nowych tożsamości dla liczb Fibonacciego i Lucasa. W rozprawie doktorskiej zdefiniowany został również ciąg -Fibonacciego, który jednocześnie uogólnia ciąg Fibonacciego, ciąg Pella, ciąg Narayana i inne ciągi typu Fibonacciego. Dla tego ciągu zostały wyznaczone różne własności, także związane z generatorami macierzowymi. Podane zostały interpretacje kombinatoryczne oraz zastosowanie tych interpretacji do dowodów tożsamości.
The main aim of this thesis is to study numbers of the Fibonacci type, in particular their applications in graphs. The first part of the thesis presents results concerning the number of all -edge colourings in unicyclic graphs. The presented results are a continuation of the research on the -index in trees. Using the properties of Fibonacci numbers, Lucas numbers and telephone numbers, the lower bound and the upper bound of the -index in unicyclic graphs are determined. We provided full characteristic of graphs achieving these extreme values. Moreover, we determined the successive extreme unicyclic graphs with respect to the number of all -edge colourings. For special classes of unicyclic graphs the exact value of the -index is determined, which resulted in obtaining new identities for Fibonacci and Lucas numbers. In the second part of the thesis we introduced and studied a new two-parameter generalization of the numbers of the Fibonacci type, named -Fibonacci numbers, which generalizes Fibonacci numbers, Pell numbers and Narayana numbers, simultaneously. We presented the properties of the -Fibonacci numbers, including their matrix representation. We gave some combinatorial interpretations of these numbers. Moreover, using these interpretations, we proved identities for the -Fibonacci numbers.
The main aim of this thesis is to study numbers of the Fibonacci type, in particular their applications in graphs. The first part of the thesis presents results concerning the number of all -edge colourings in unicyclic graphs. The presented results are a continuation of the research on the -index in trees. Using the properties of Fibonacci numbers, Lucas numbers and telephone numbers, the lower bound and the upper bound of the -index in unicyclic graphs are determined. We provided full characteristic of graphs achieving these extreme values. Moreover, we determined the successive extreme unicyclic graphs with respect to the number of all -edge colourings. For special classes of unicyclic graphs the exact value of the -index is determined, which resulted in obtaining new identities for Fibonacci and Lucas numbers. In the second part of the thesis we introduced and studied a new two-parameter generalization of the numbers of the Fibonacci type, named -Fibonacci numbers, which generalizes Fibonacci numbers, Pell numbers and Narayana numbers, simultaneously. We presented the properties of the -Fibonacci numbers, including their matrix representation. We gave some combinatorial interpretations of these numbers. Moreover, using these interpretations, we proved identities for the -Fibonacci numbers.
Description
Wydział Matematyki i Informatyki
Sponsor
Keywords
liczby Fibonacciego, krawędziowe kolorowanie, liczby typu Fibonacciego, Fibonacci numbers, edge colouring, numbers of the Fibonacci type