3-valentni vozliščno tranzitivni grafi : delo diplomskega seminarja

Škvarč, Teja (author), Potočnik, Primož (mentor)

Cilj diplomskega dela je določiti vse kubične vozliščno tranzitivne grafe do nekega v naprej danega reda. $G$-vozliščno tranzitivni graf je graf, za katerega velja, da podgrupa $G$ grupe avtomorfizmov grafa deluje tranzitivno na množico vozlišč. Glede na število orbit delovanja vozliščnega stabilizatorja $G_v$ na soseščini $\Gamma(v)$ ločimo tri skupine kubičnih vozliščno tranzitivnih grafov. Prvo skupino, kjer imamo samo eno orbito, nam trditev, ki pravi, da ima delovanje vozliščnega stabilizatorja na soseščini enako orbit kot delovanje grupe $G$ na lokih grafa, poveže s kubičnimi ločno tranzitivnimi grafi. Drugo skupino, kjer imamo tri orbite, nam Sabidussijev izrek poveže s Cayleyjevimi grafi. Tretjo skupino, kjer imamo dve orbiti, pa povežemo s tetravalentnimi ločno tranzitivnimi grafi.

• Language: Slovenian
• Keywords: kubični grafi, vozliščno tranzitivni grafi, ločno tranzitivni grafi, delovanje grupe na množico, stabilizator, orbita, avtomorfizmi grafa, hiperkocke, Cayleyjevi grafi, Sabidussijev izrek, Magma, dekompozicija grafa na cikle, popolno prirejanje.
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2019
• PID: 20.500.12556/RUL-110747
• UDC: 519.1
• COBISS.SI-ID: 18820953
• Publication date in RUL: 19.09.2019

ŠKVARČ, Teja, 2019, 3-valentni vozliščno tranzitivni grafi : delo diplomskega seminarja [online]. Bachelor’s thesis. [Accessed 13 August 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=110747

Secondary language

• Language: English
• Title: Cubic vertex-transitive graphs

Abstract

The paper's aim is to determinate all cubic vertex-transitive graphs on up to certain order which is given in advance. A graph is $G$-vertex-transitive graph, if subgroup $G$ of graph's group of automorphism acts transitively on its vertex-set. Based on the number of orbits of the vertex-stabiliser $G_v$ in its action on the neighbourhood $\Gamma(v)$ we separate cubic vertex-transitive graphs into three groups. The first group is the group of graphs with only one orbit. Theorem, stating that the action of vertex-stabiliser on the neighbourhood has the same number of orbits as the action of group $G$ on arc-set, connects first group's graphs with cubic arc-transitive ones. The second group is the group of graphs with three orbits. Sabidussi's theorem connets second group's graphs with Cayley's graphs. The last group is the group of graphs with two orbits. Graphs from this group are connected with tetravalent arc-transitive graphs.

• Keywords: cubic graphs, vertex-transitive graphs, arc-transitive graphs, group acting on set, stabiliser, orbit, graphs automorphisms, hypercubes, Cayley's graphs, Sabidussi's theorem, Magma, cycle decomposition of graph, perfect matching.