Recurrences and graphs of recurrences

doctoral thesis

• Title (croatian): Rekurzije i grafovi rekurzija
• Author: Luka Podrug
• Mentor: Tomislav Došlić (mentor)
• Committee member: Vedran Krčadinac (predsjednik povjerenstva)
• Committee member: Snježana Majstorović Ergotić (član povjerenstva)
• Committee member: Tomislav Došlić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2024-05-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics
• Universal decimal classification (UDC): 51 - Mathematics

Abstract

In the first part of the dissertation, we count tilings of narrow strips in the hexagonal grid with a given number and type of tiles and investigate identities involving the obtained enumerating sequences. On the same substrate, we also study the number of tilings in which both the number and the shape of tiles are free. In both cases, the enumerating sequences satisfy linear recurrences with constant coefficients. In contrast to the first part where linear recurrences are obtained as a solution to the problem, the central part of the work uses them as a starting point. Namely, it is dedicated to the family of graphs that generalize Fibonacci cubes and whose number of vertices satisfies the recursion \(s_n = as_{n−1} + s_{n−2}\). We determine basic enumerative and metric properties and show that the family retains many desirable properties of Fibonacci cubes. Canonical decomposition and distribution of degrees will be investigated, as well as the existence of Hamiltonian paths and cycles. In the last part, we explore the possibility of extending the family of graphs to the Horadam recursion \(s_n = as_{n−1} +bs_{n−2}\).

Abstract (croatian)

U prvom dijelu rada prebrojavamo popločenja uskih traka šesterokutne mreže s unaprijed poznatim brojem pločica određenog tipa i istražujemo mogućnost dobivanja identiteta o nizovima koje tako dobivamo. Preciznije, istražujemo na koliko se načina može popločati uska šesterokutna mreža koristeći samo monomere i dimere, a s unaprijed određenim brojem dimera. Nadalje, proučavamo sličan problem, ali umjesto horizontalnih dimera koristimo trimere, dobivene od tri uzastopna šesterokuta na mreži. Na istom supstratu promatramo i ukupni broj podjela promatrane šesterokutne mreže, tj. broj popločenja u kojima su i broj i oblik pločica proizvoljni. U ovom slučaju dobivamo jednostavan odgovor, broj načina na koji možemo podijeliti usku šesterokutnu mrežu odgovara Fibonaccijevim brojevima neparnog indexa. U svim slučajevima dobivaju se nizovi zadani linearnim rekurzijama. Središnji dio rada posvećen je familiji grafova koja poopćuje Fibonaccijeve kocke. Broj vrhova \(sn\) u grafovima takve familije također zadovoljava linearnu rekurziju, \(s_n = as_{n−1} + s_{n−2}\). Određujemo njihova osnovna enumerativna i metrička svojstava te pokazujemo da familija zadržava mnoga poželjna svojstva Fibonaccijevih kocaka. Određivanjem kanonske dekompozicije pokazujemo da se grafovi mogu dekomponirati u više grafova iste vrste, a manje dimenzije. Također, dekomponirajući ih u rešetke, pronalazimo još jednu vezu promatrane familije i Fibonaccijevih kocki. Određujemo i raspodjelu stupnjeva vrhova i dajemo nužne uvjete za postojanje Hamiltonovih putova i ciklusa. U posljednjem dijelu rada istražujemo mogućnost proširenja familije grafova na Horadamovu rekurziju \(s_n = as_{n−1} +bs_{n−2}\), i pokazujemo da se mnoga svojstva Fibonaccijevih i metalnih kocaka nasljeđuju za grafove te familije.

• Keywords: tilings; Fibonacci cubes; Horadam recursion
• Keywords (croatian): popločenja; Fibonaccijeve kocke; Horadamova rekurzija
• Language: english
• URN:NBN: urn:nbn:hr:217:529626
• Promotion: 2024
• Study programme: Title: Doctoral study; Study programme type: university; Study level: postgraduate; Academic / professional title: doktor/doktorica u području prirodnih znanosti (doktor/doktorica u području prirodnih znanosti)
• Type of resource: Text
• Extent: v, 128 str.
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-06-27 08:41:57