izpis_h1_title_alt

Metric properties of Sierpiński graphs : doctoral thesis
ID Zemljič, Sara Sabrina (Author), ID Klavžar, Sandi (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (886,60 KB)
MD5: 10E746C1BFF5692CF517279498A950B8
PID: 20.500.12556/rul/8ef9f4cd-d5d1-4f1a-b486-ac30a1f3bd89

Abstract
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 This link opens in a new window
UDC:519.17(043.3)
COBISS.SI-ID:17047129 This link opens in a new window
Publication date in RUL:24.10.2017
Views:1379
Downloads:343
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

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

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back