O simetričnih Nest grafih : magistrsko delo

Vasiljević, Gorazd (author), Šparl, Primož (mentor)

Magistrsko delo sodi na področje algebraične teorije grafov. V tej veji teorije grafov nas pogosto zanimajo t. i. avtomorfizmi (simetrije) grafov, torej permutacije množice vozlišč grafa, ki ohranjajo sosednosti. Pri tem je naš cilj pogosto klasifikacija vseh grafov z nekimi danimi simetrijskimi lastnostmi. Pri posebej »lepih« grafih velja, da za poljuben par vozlišč obstaja avtomorfizem, ki eno vozlišče preslika v drugo (t. i. grupa avtomorfizmov grafa deluje tranzitivno na množico vozlišč). Pravimo, da so taki grafi vozliščno tranzitivni. Na podoben način je lahko graf povezavno tranzitiven, če grupa avtomorfizmov deluje tranzitivno na množico njegovih povezav in je ločno tranzitiven (oziroma simetričen), če grupa avtomorfizmov deluje tranzitivno na množico njegovih lokov. Bicirkulant je graf, ki dopušča avtomorfizem z dvema orbitama iste dolžine. Za začetek preučevanja simetrij bicirkulantov štejemo rezultate Fruchta, Graverja in Watkinsa iz leta 1971, ki so preučili družino t. i. Posplošenih Petersenovih grafov in klasificirali vse njene vozliščno in povezavno tranzitivne člane. Naslednji korak je leta 2008 storil Wilson, ki je opravil velik del klasifikacije povezavno tranzitivnih Rozetnih grafov, njegovo delo pa so dve leti kasneje dokončali Kovács, Kutnar in Marušič. Podobno so Arroyo, Hubard, Kutnar, O'Reilly in Šparl leta 2015 klasificirali vse simetrične Tabačjn grafe. V magistrskem delu vpeljemo posplošitev Posplošenih Petersenovih grafov na stopnjo 6. Gre za doslej še neraziskano družino bicirkulantov. Pripadajoče grafe poimenujemo Nest grafi. Glavni namen magistrskega dela je začetek klasifikacije simetričnih Nest grafov, pri čemer storimo nekaj prvih, pomembnih korakov. Poleg predstavitve same družine Nest grafov, v kateri pokažemo nekaj njihovih osnovnih lastnosti in dejstev, povezanih z njimi, se v nadaljevanju osredotočimo predvsem na njihove simetrijske lastnosti. Na podlagi rezultatov programskega paketa Magma identificiramo nekatere družine ločno tranzitivnih Nest grafov in za njihove člane dokažemo, da so res simetrični. Kot zelo pomemben rezultat magistrsko delo predstavi skoraj popolno klasifikacijo simetričnih Nest grafov ožine 3.

• Language: Slovenian
• Keywords: teorija grafov, bicirkulant, avtomorfizem, Nest graf, ločno tranzitiven graf
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: PEF - Faculty of Education
• Publisher: [G. Vasiljević]
• Year: 2017
• Number of pages: 67 str.
• PID: 20.500.12556/RUL-92689
• UDC: 519.17(043.2)
• COBISS.SI-ID: 11588681
• Publication date in RUL: 24.08.2017

Secondary language

• Language: English
• Title: On symmetric Nest graphs

Abstract

This MSc thesis deals with certain topics from algebraic graph theory. In this field of mathematics, we usually study so-called graph automorphisms (also called symmetries), which are permutations of the graph's vertex set, perserving adjacency. Quite often, the goal is to classify all of the graphs with chosen symmetry properties. There exist graphs, which are symmetric enough, so that their automorphism group acts transitively on their vertex set. This means that for any pair of vertices of the graph there is an automorphism, mapping one vertex to the other. Such graphs are called vertex-transitive. Similarly, a graph is edge-transitive, if its automorphism group acts transitively on its edge set and is arc-transitive if its automorphism group acts transitively on its arc set. A bicirculant is a graph, admitting an automorphism with two orbits of the same length. Frucht, Graver and Watkins were the first to systematically study symmetries of Generalized Petersen Graphs (1971) and classifing all vertex and edge-transitive ones. In this way they began the study of symmetries of bicirculants. The next step was done by Wilson in 2008, who made an important step towards the classification of edge-transitive Rose-Window graphs by identifying four families of such graphs. His work was completed two years later by Kovács, Kutnar and Marušič. Similarly, Arroyo, Hubard, Kutnar, O'Reilly and Šparl classified all arc-transitive Tabačjn graphs in 2015. In this thesis, we introduce 6-valent generalization of Generalized Petersen graphs. The chosen family of graphs was not a subject of any research until now. We name the corresponding graphs as Nest graphs. The main goal of the thesis is to start a classification of symmetric Nest graphs, where we make a few first, but, nonetheless, important steps. We firstly present the family of Nest graphs, along with some of their basic properties and facts about them, where we focus on their symmetry properties. Based on the results, obtained with the aid of the computer package Magma, we then identify some families of symmetric Nest graphs and for each of their members prove that they indeed are symmetric Nest graphs. One of the key results of the thesis is also an almost completed classification of symmetric Nest graphs of girth 3.

• Keywords: mathematics, matematika