Cycles and symmetries in graphs : doctoral thesis

Lekše, Maruša (author), Potočnik, Primož (mentor), Toledo Roy, Micael Alexi (comentor)

This thesis explores the interplay between cycles and symmetry in finite graphs, studying several sets of cycles that are invariant under the action of a group of automorphisms (girth cycles, face cycles and consistent cycles), and the constraints they impose on the graph and its automorphism group. We classify cubic vertex-transitive graphs of girth $7$, extending the existing classifications for girth up to $6$ due to Potočnik and Vidali and to Eiben, Šparl and Jajcay. Additionally, we observe that every vertex-transitive map of type $\{7,3\}$ is rotary. This observation motivates a broader question: under what conditions on the signature does every vertex-transitive group of automorphisms of every map of that signature act as a rotary group? We give a complete characterization: every map of type $\{p,q\}$ has the property that every vertex-transitive group of automorphisms is rotary if and only if $q$ is odd and ${\rm gcd}(p,q!) = 1$. Next we study consistent cycles in arc-transitive graphs. A cycle in a graph is $G$-consistent if some automorphism in $G$ cyclically permutes its vertices by one step. We give sufficient conditions for the existence of a $G$-consistent walk with trivial pointwise stabilizer. These conditions hold whenever the local group is weakly $p$-subregular, and also whenever the graph has valence at most $4$. As an application, we show that every vertex-transitive group of automorphisms of a connected $d$-valent graph can always be generated by the stabilizer of any consistent walk, plus at most $d$ automorphisms. We address the spouse-loving variant of the Oberwolfach problem. We develop techniques for transforming solutions of ${\rm OP}$ into solutions of ${\rm OP}^+$, and use them to completely resolve the two-table case: ${\rm OP}^+(\ell_1, \ell_2)$ has a solution if and only if $\ell_1 + \ell_2$ is even and $(\ell_1, \ell_2)$ is not $(2, 2)$ or $(3, 3)$. Finally, we address a question from the theory of maniplexes on symmetry type graphs. Can every map be obtained as the quotient of some map by its full automorphism group?

• Language: English
• Keywords: Vertex-transitive graphs, arc-transitive graphs, girth-regularity, rotary maps, consistent cycles, Oberwolfach problem, symmetry type graph conjecture
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2026
• PID: 20.500.12556/RUL-189056
• UDC: 519.17
• COBISS.SI-ID: 293282051
• Publication date in RUL: 01.10.2026

Secondary language

• Language: Slovenian
• Title: Cikli in simetrije v grafih

Abstract

To doktorsko delo raziskuje preplet med cikli in simetrijo v končnih grafih. Proučuje več množic ciklov, ki so invariantne za delovanje grupe avtomorfizmov (ožinski cikli, lica zemljevidov in konsistentni cikli), ter omejitve, ki jih ti cikli zahtevajo od grafa in njegove grupe avtomorfizmov. Klasificiramo kubične vozliščno tranzitivne grafe ožine $7$, s čimer razširjamo obstoječe klasifikacije za ožine do vključno $6$, ki sta jih dokazala Potočnik in Vidali, ter Eiben, Šparl in Jajcay. Opazimo, da je vsak vozliščno tranzitiven zemljevid tipa $\{7,3\}$ rotacijski. To opažanje motivira širše vprašanje: pod kakšnimi pogoji je vsaka vozliščno tranzitivna grupa avtomorfizmov zemljevida rotacijska? Podamo karakterizacijo: vsak zemljevid tipa $\{p,q\}$ ima lastnost, da je vsaka vozliščno tranzitivna grupa avtomorfizmov rotacijska, če in samo če je $q$ lih in je ${\rm gcd}(p,q!) = 1$. Nato proučujemo konsistentne cikle v ločno tranzitivnih grafih. Cikel v grafu je $G$-konsistenten, če nek avtomorfizem v $G$ ciklično permutira njegova vozlišča za en korak. Podamo zadostne pogoje za obstoj $G$-konsistentnega sprehoda s trivialnim stabilizatorjem. Ti pogoji veljajo vedno, ko je lokalna grupa šibko $p$-subregularna, ali pa, ko ima graf stopnjo največ $4$. Pokažemo tudi, da lahko vsako vozliščno tranzitivno grupo avtomorfizmov $d$-valentnega grafa generiramo s stabilizatorjem katerega koli konsistentnega sprehoda in največ d drugimi avtomorfizmi. Obravnavamo tudi različico Oberwolfachovega problema z zakonskimi pari. Razvijemo tehnike za spremembo rešitev problema ${\rm OP}$ v rešitve problema ${\rm OP}^+$. Uporabimo jih za popolno rešitev primera z dvema mizama: ${\rm OP}^+(\ell_1, \ell_2)$ ima rešitev natanko tedaj, ko je $\ell_1 + \ell_2$ sod in $(\ell_1, \ell_2)$ ni $(2, 2)$ ali $(3, 3)$. Na koncu obravnavamo vprašanje iz teorije manipleksov za grafe simetrijskega tipa. Ali je mogoče vsak zemljevid dobiti kot kvocient nekega zemljevida z njegovo polno grupo avtomorfizmov?

• Keywords: vozliščno tranzitivni grafi, ločno tranzitivni grafi, ožinska regularnost, rotacijski zemljevidi, konsistentni cikli, Oberwolfachov problem, domneva o grafih simetrijskega tipa