magistrsko delo
Ksenija Rozman (Avtor), Primož Šparl (Mentor)

Povzetek

Vsebina magistrskega dela sodi na področje algebraične teorije grafov, kjer se med drugim ukvarjamo s simetrijami v grafih. Simetrije oziroma avtomorfizmi v grafu so permutacije množice vozlišč, ki ohranjajo sosednosti. Če v grafu obstajajo taki avtomorfizmi, da z njimi lahko poljubno vozlišče preslikamo v vsako drugo vozlišče, pravimo, da je graf vozliščno tranzitiven. Primeri vozliščno tranzitivnih grafov so Cayleyevi grafi. Cayleyevi grafi so, še posebej kubični, ravno zaradi lepih simetrijskih lastnosti priljubljen predmet raziskovanja v zadnjih nekaj desetletjih. V magistrskem delu nas zanimajo simetrije specifične družine kubičnih grafov, to so HTG grafi (ang. Honeycomb Toroidal Graphs). Odvisni so od treh parametrov - m; n in l in imajo mn vozlišč. Po uvodni predstavitvi teoretičnih izhodišč, ki jih bralec potrebuje za razumevanje magistrskega dela, najprej definiramo HTG grafe in si pogledamo nekaj njihovih preprostih strukturnih lastnosti. Med drugim se prepričamo, da so vsi dvodelni in vozliščno tranzitivni ter ožine največ 6. V nekaterih izmed njih najdemo tudi 4-cikle in pokažemo, da obstajajo le tri družine HTG grafov ožine 4, do izomorfizma natančno. V nadaljevanju dokažemo, da so HTG grafi Cayleyevi grafi pripadajočih posplošenih diedrskih grup, pri čemer za povezavno množico vzamemo množico treh involucij. S tem jih umestimo v dobro znano družino (vozliščno tranzitivnih) grafov, hkrati pa lahko zaradi tega povezave takšnih kubičnih Cayleyevih grafov naravno pobarvamo s tremi barvami tako, da se v vsakem vozlišču stikajo vse tri barve. Avtomorfizme, ki te barve ohranjajo ali jih permutirajo, imenujemo »barvni« avtomorfizmi. HTG grafi v zadnjih desetletjih vzbujajo zanimanje številnih raziskovalcev, tako na področju teorije grafov kot tudi na področju računalništva. Simetrije teh grafov so bile do nedavnega še neraziskane. Brian Alspach je v [1] zbral nekaj znanih rezultatov o HTG grafih in objavil nekaj še nerešenih vprašanj, povezanih z njimi. Dve od teh vprašanj se nanašata na simetrije omenjenih grafov in na ti dve se osredotočimo v magistrskem delu. Naš glavni namen je raziskati, koliko simetrij premorejo HTG grafi v odvisnosti od vseh treh parametrov in kateri od njih imajo najmanjšo možno grupo avtomorfizmov. V grobem vse HTG grafe razdelimo v dve skupini. V prvi so tisti, ki premorejo le barvne avtomorfizme, v drugi pa tisti, ki poleg teh premorejo še druge. Slednji so zanimivi predvsem zato, ker niso izjemni le med HTG grafi, ampak imajo posebno mesto tudi v okviru vseh kubičnih grafov. Za te bolj natančno raziščemo, od kje izvira tako velika grupa avtomorfizmov.

Ključne besede

HTG grafi;Cayleyev graf;posplošena diedrska grupa;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UL PEF - Pedagoška fakulteta
Založnik: [K. Rozman]
UDK: 519.17(043.2)
COBISS: 90256131 Povezava se bo odprla v novem oknu
Št. ogledov: 6030
Št. prenosov: 82
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: Angleški jezik
Sekundarni naslov: Symmetries of the HTG graphs
Sekundarni povzetek: The topic of this MSc Thesis arises from the field of algebraic graph theory, where, among other things, we deal with graph symmetries. Symmetries, also called graph automorphisms, are permutations of vertices, which preserve adjacency. If there are automorphisms that ensure we can map one vertex into any other one the graph is said to be vertex-transitive. Examples of vertextransitive graphs are Cayley graphs. Cayley graphs, and cubic Cayley graphs in particular, have been desireable research object over the last couple of decades due to their high degree of symmetry. In the MSc Thesis we are interested in symmetries of members of a specific family of cubic graphs, called Honeycomb Toroidal Graphs (denoted by HTG). They are determined by three parameters - m, n and l and have mn vertices. After the preliminary presentation of the prerequisite theory we first define Honeycomb Toroidal Graphs and present some of their basic structural properties. We show, among other things, that all HTG graphs are bipartite, vertex-transitive and are of girth at most 6. Some of them also possess cycles of length 4. We show that there are exactly three families of HTG graphs of girth 4. Later on we provide the proof of each HTG graph being isomorphic to a Cayley graph on an appropriate generalized dihedral group with respect to the connection set of three involutions, thereby placing them in a well-known family of (vertex-transitive) graphs. Moreover, the edges of such Cayley graphs can be naturally colored with three colors in a way that the three edges incident to any vertex are of distinct colors. Automorphisms which preserve or permute these colors are called “color” automorphisms. The Honeycomb Toroidal Graphs have received considerable attention over the last few decades not only by mathematicians but also by computer scientists. Until recently, the question of their symmetries hasn't been explored much. In a recent survey [1] Brian Alspach gathered most of the known results on HTG graphs and discussed a few research problems regarding them. In the MSc Thesis we focus on two of them, both of which concern symmetries of these graphs. Our main purpose is to determine the order of the automorphism group of each HTG graph in terms of all three parameters and to classify those with the smallest possible group of automorphisms. We divide the family of all HTG graphs roughly into two parts. The first part admits only color automorphisms while the second one admits automorphisms that are not color permuting. The main point of interest of the latter is that they are exceptional not only among HTG graphs but also among all cubic graphs. The origins of large automorphism groups of these graphs are examined more closely.
Sekundarne ključne besede: Teorija grafov;Avtomorfizmi;Univerzitetna in visokošolska dela;
Vrsta datoteke: application/pdf
Vrsta dela (COBISS): Magistrsko delo/naloga
Komentar na gradivo: Univ. v Ljubljani, Pedagoška fak., Poučevanje, Predmetno poučevanje
Strani: 74 str.
ID: 14020062