Liczby typu Fibonacciego, ich własności i zastosowania do problemów zliczania w grafach

Thumbnail Image

Date

2021

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.

Description

Wydział Matematyki i Informatyki

Sponsor

Keywords

liczby Fibonacciego, krawędziowe kolorowanie, liczby typu Fibonacciego, Fibonacci numbers, edge colouring, numbers of the Fibonacci type

Citation

ISBN

DOI

Title Alternative

Rights Creative Commons

Creative Commons License

Uniwersytet im. Adama Mickiewicza w Poznaniu
Biblioteka Uniwersytetu im. Adama Mickiewicza w Poznaniu
Ministerstwo Nauki i Szkolnictwa Wyższego