doctoral thesis
Sara Sabrina Zemljič (Avtor), Sandi Klavžar (Mentor)

Povzetek

V disertaciji preučujemo metrične lastnosti grafov Sierpińskega. Ti tvorijo 2-parametrično družino grafov, podobno grafom Hanojskega stolpa. Grafe Sierpińskega srečamo na različnih matematičnih področjih kot tudi v drugih vedah. Najprej predstavimo družino grafov Sierpińskega in njihove različice. Te družine so poznane pod različnimi imeni, nekateri različni grafi pa si v literaturi delijo ime. V ta namen standardiziramo njihove oznake in imena, da bi se izognili zmedi pri nadaljnjem raziskovalnem delu. Naslednji korak je predstavitev znanih rezultatov o grafih Sierpińskega. Eno poglavje disertacije v celoti namenjamo metričnim lastnostim grafov Sierpińskega, kjer najprej navedemo z metričnimi lastnostmi povezane znane rezultate. Posebno izpostavimo dobro znano lemo o razdalji in izrek o razdalji med poljubnima dvema vozliščema. Ker je ta razdalja določena z minimumom, izpeljemo izboljšane rezultate za razdalje do skoraj ekstremnih vozlišč. Natančneje povedano, razdaljo med poljubnim vozliščem in skoraj ekstremnim vozliščem na grafu Sierpińskega izrazimo z eksplicitno formulo. Poglavje zaključimo z določitvijo metrične dimenzije grafov Sierpińskega. Da bi bolje razumeli strukturo grafov Sierpińskega, na koncu preučujemo različne vložitve. Zaradi njihove povezave s Hanojskim stolpom si najprej ogledamo vložitve v grafe Hanojskega stolpa. Prav tako določimo kanonično metrično reprezentacijo in inducirane vložitve. Za slednje vpeljemo Hammingovo dimenzijo in določimo njene meje za družino grafov Sierpińskega. Disertacijo zaključimo z navedbo nekaterih odprtih problemov.

Ključne besede

Sierpiński graph;Sierpiński-type graph;distance;almost-extreme vertex;distance of a vertex;metric dimension;Switching Tower of Hano;canonical metric representation;Hamming dimension;induced embedding;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 2.08 - Doktorska disertacija
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
Založnik: [S. S. Zemljič]
UDK: 519.17(043.3)
COBISS: 17047129 Povezava se bo odprla v novem oknu
Št. ogledov: 851
Št. prenosov: 313
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Metrične lastnosti grafov Sierpińskega
Sekundarni povzetek: In this thesis we study the metric properties of Sierpiński graphs. Sierpiński graphs form a two-parametric family of graphs similar to Hanoi graphs that originate in the Tower of Hanoi puzzle. Sierpiński graphs can be found in various areas of mathematics and elsewhere. First we introduce the family of Sierpiński graphs and their variants. These families have been known under various names, and sometimes vice versa - different graphs under the same name. We therefore standardize their notations and names to avoid confusion in the future. Next we summarize what has already been studied on Sierpiński graphs. One chapter of the thesis is completely devoted to metric properties of Sierpiński graphs, where we first list known related results, in particular we state the distance lemma and the theorem about the distance between arbitrary two vertices. Since this distance is expressed with a minimum, we give improved results on distances in Sierpiński graphs for almost-extreme vertices. Namely, the distance between an arbitrary vertex and an almost-extreme vertex in a Sierpiński graph can be expressed with a closed formula. We conclude this part with determining the metric dimension of Sierpiński graphs. To better understand the structure of Sierpiński graphs we study various embeddings, beginning with the embeddings into Hanoi graphs. We also determine the canonical metric representation and induced embeddings. For the latter type of embeddings, we introduce the Hamming dimension and bound it for Sierpiński graphs. We conclude with some open problems.
Sekundarne ključne besede: graf Sierpińskega;graf tipa Sierpińskega;razdalja;skoraj ekstremno vozlišče;razdalja vozlišča;metrična dimenzija;graf hanojskega stolpa;zamenjevalni hanojski stolp;kanonična metrična reprezentacija;Hammingova dimenzija;inducirana vložitev;
Vrsta dela (COBISS): Doktorsko delo/naloga
Komentar na gradivo: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 3. stopnja
Strani: 101 str.
ID: 10865392