Metric properties of Sierpiński graphs : doctoral thesis

Zemljič, Sara Sabrina (author), Klavžar, Sandi (mentor)

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.

• Language: English
• Keywords: Sierpiński graph, Sierpiński-type graph, distance, almost-extreme vertex, distance of a vertex, metric dimension, switching Tower of Hanoi, canonical metric representation, Hamming dimension, induced embedding
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FMF - Faculty of Mathematics and Physics
• Place of publishing: Ljubljana
• Publisher: [S. S. Zemljič]
• Year: 2014
• Number of pages: 101 str.
• PID: 20.500.12556/RUL-95854
• UDC: 519.17(043.3)
• COBISS.SI-ID: 17047129
• Publication date in RUL: 24.10.2017

Secondary language

• Language: Slovenian
• Title: Metrične lastnosti grafov Sierpińskega

Abstract

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.

• Keywords: 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