ISSN 2590-9770
The Art of Discrete and Applied Mathematics 7 (2024) #P2.06
https://doi.org/10.26493/2590-9770.1617.83c
(Also available at http://adam-journal.eu)
Symmetries of the Woolly Hat graphs*
Leah Wrenn Berman
University of Alaska Fairbanks, Department of Mathematics and Statistics,
Fairbanks, AK, USA
Sergio Hiroki Koike Quintanar
National Autonomous University of Mexico, Institute of Mathematics, Mexico City, Mexico
Elías Mochán
Northeastern University, Department of Mathematics, Boston, MA, USA
Alejandra Ramos-Rivera
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Primož Šparl†
University of Ljubljana, Faculty of Education, Ljubljana, Slovenia
University of Primorska, Institute Andrej Marušič, Koper, Slovenia
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Stephen E. Wilson
Northern Arizona University, Department of Mathematics and Statistics,
Flagstaff, AZ, USA
Received 2 February 2023, accepted 7 September 2023, published online 5 October 2024
Abstract
A graph is edge-transitive if the natural action of its automorphism group on its edge set
is transitive. An automorphism of a graph is semiregular if all of the orbits of the subgroup
generated by this automorphism have the same length. While the tetravalent edge-transitive
graphs admitting a semiregular automorphism with only one orbit are easy to determine,
those that admit a semiregular automorphism with two orbits took a considerable effort
*The authors are grateful to Primož Potočnik for fruitful conversations on the topic. They would also like to
thank the organizers of the 2017 CMO workshop Symmetries of Discrete Structures in Geometry held in Oaxaca,
Mexico, the 2018 and 2022 SIGMAP conferences held in Morelia, Mexico, and Fairbanks, USA, respectively, and
the 2022 Workshop on Symmetries of Graphs, held in Kranjska Gora, Slovenia, during which a considerable part
of the research that lead to the results of this paper was performed.
†Corresponding author. The author acknowledges financial support by the Slovenian Research Agency (re-
search program P1-0285 and research projects J1-2451 and J1-3001).
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
and were finally classified in 2012. Of the several possible different “types” of potential
tetravalent edge-transitive graphs admitting a semiregular automorphism with three orbits,
only one “type” has thus far received no attention. In this paper we focus on this class of
graphs, which we call the Woolly Hat graphs. We prove that there are in fact no edge-
transitive Woolly Hat graphs and classify the vertex-transitive ones.
Keywords: Edge-transitive, vertex-transitive, tricirculant, Woolly Hat graph.
Math. Subj. Class.: 05C25, 20B25
E-mail addresses: lwberman@alaska.edu (Leah Wrenn Berman), hiroki.koike@im.unam.mx (Sergio Hiroki
Koike Quintanar), j.mochanquesnel@northeastern.edu (Elías Mochán), alejandra.ramosrivera@fmf.uni-lj.si
(Alejandra Ramos-Rivera), primoz.sparl@pef.uni-lj.si (Primož Šparl), stephen.wilson@nau.edu (Stephen
E. Wilson)
ISSN 2590-9770
The Art of Discrete and Applied Mathematics 7 (2024) #P2.06
https://doi.org/10.26493/2590-9770.1617.83c
(Dostopno tudi na http://adam-journal.eu)
Simetrije grafov volnenih kap*
Leah Wrenn Berman
University of Alaska Fairbanks, Department of Mathematics and Statistics,
Fairbanks, AK, USA
Sergio Hiroki Koike Quintanar
National Autonomous University of Mexico, Institute of Mathematics, Mexico City, Mexico
Elías Mochán
Northeastern University, Department of Mathematics, Boston, MA, USA
Alejandra Ramos-Rivera
Inštitut za matematiko, fiziko in mehaniko, Ljubljana, Slovenija
Primož Šparl†
Univerza v Ljubljani, Pedagoška fakulteta, Ljubljana, Slovenija
Univerza na Primorskem, Inštitut Andreja Marušiča, Koper, Slovenija
Inštitut za matematiko, fiziko in mehaniko, Ljubljana, Slovenija
Stephen E. Wilson
Northern Arizona University, Department of Mathematics and Statistics,
Flagstaff, AZ, USA
Prejeto 2. februarja 2023, sprejeto 7. septembra 2023, objavljeno na spletu 5. oktobra 2024
Povzetek
Graf je povezavno tranzitiven, če je naravno delovanje njegove grupe avtomorfizmov na
njegovi množici povezav tranzitvno. Avtomorfizem grafa je semiregularen, če imajo vse or-
bite podgrupe, generirane s tem avtomorfizmom, isto dolžino. Medtem ko je tetravalentne
povezavno tranzitivne grafe, ki dopuščajo semiregularni avtomorfizem z eno samo orbito,
*Avtorji so hvaležni Primožu Potočniku za plodne pogovore na temo. Prav tako bi se radi zahvalili organiza-
torjem delavnice CMO 2017 Simetrije diskretnih struktur v geometriji, ki je potekala v Oaxaci, Mehika, konferenc
SIGMAP 2018 in 2022, ki sta potekali v Moreliji, Mehika, in Fairbanksu, ZDA, in Delavnice o simetrijah grafov,
ki je leta 2022 potekala v Kranjski Gori v Sloveniji, med katero je bil opravljen precejšen del raziskav, ki so
privedle do rezultatov tega prispevka.
†Kontaktni avtor. Avtor se zahvaljuje za finančno podporo Javne agencije za raziskovalno dejavnost RS
(raziskovalni program P1-0285 in raziskovalna projekta J1-2451 in J1-3001).
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/
enostavno določiti, so tisti, ki dopuščajo semiregularni avtomorfizem z dvema orbitama, za-
htevali precej dela, končno so bili klasificirani leta 2012. Od več možnih različnih “tipov”
potencialnih tetravalentnih povezavno tranzitivnih grafov, ki dopuščajo semiregularen av-
tomorfizem s tremi orbitami, samo en “tip” do sedaj ni bil deležen nobene pozornosti.
V tem članku se osredotočamo na ta razred grafov, ki ga imenujemo grafi volnenih kap.
Dokažemo, da v resnici ni nobenih povezavno tranzitivnih grafov volnenih kap in klasifi-
ciramo točkovno tranzitivne.
Ključne besede: Povezavno tranzitiven, točkovno tranzitiven, tricirkulant, grafi volnenih kap.
Math. Subj. Class.: 05C25, 20B25
E-poštni naslovi: lwberman@alaska.edu (Leah Wrenn Berman), hiroki.koike@im.unam.mx (Sergio Hiroki
Koike Quintanar), j.mochanquesnel@northeastern.edu (Elías Mochán), alejandra.ramosrivera@fmf.uni-lj.si
(Alejandra Ramos-Rivera), primoz.sparl@pef.uni-lj.si (Primož Šparl), stephen.wilson@nau.edu (Stephen
E. Wilson)