ISSN 2590-9770
The Art of Discrete and Applied Mathematics 3 (2020) #P1.04
https://doi.org/10.26493/2590-9770.1279.02c
(Also available at http://adam-journal.eu)
A new generalization of generalized Petersen
graphs*
Katarína Jasenčáková
Faculty of Management Science and Informatics, University of Žilina, Žilina, Slovakia
Robert Jajcay†
Faculty of Mathematics, Physics and Informatics, Comenius University, Bratislava,
Slovakia; also affiliated with Faculty of Mathematics, Natural Sciences and Information
Technology, University of Primorska, Koper, Slovenia
Tomaž Pisanski‡
Faculty of Mathematics, Natural Sciences and Information Technology,
University of Primorska, Koper, Slovenia; also affiliated with
FMF and IMFM, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia
Received 30 November 2018, accepted 13 August 2019, published online 27 July 2020
Abstract
We discuss a new family of cubic graphs, which we call group divisible generalised Pe-
tersen graphs (GDGP -graphs), that bears a close resemblance to the family of generalised
Petersen graphs, both in definition and properties. The focus of our paper is on determin-
ing the algebraic properties of graphs from our new family. We look for highly symmetric
graphs, e.g., graphs with large automorphism groups, and vertex- or arc-transitive graphs.
In particular, we present arithmetic conditions for the defining parameters that guarantee
that graphs with these parameters are vertex-transitive or Cayley, and we find one arc-
transitive GDGP -graph which is neither a CQ graph of Feng and Wang, nor a generalised
Petersen graph.
Keywords: Generalised Petersen graph, arc-transitive graph, vertex-transitive graph, Cayley graph,
automorphism group.
Math. Subj. Class.: 05C25
*We thank the anonymous referee for all the helpful and insightful comments.
†Author acknowledges support by the projects VEGA 1/0596/17, VEGA 1/0719/18, VEGA 1/0423/20,
APVV-15-0220, and by the Slovenian Research Agency (research projects N1-0038, N1-0062, J1-9108).
‡The work is supported in part by the Slovenian Research Agency (research program P1-0294 and research
projects N1-0032, J1-9187, J1-1690, N1-0140), and in part by H2020 Teaming InnoRenew CoE.
E-mail addresses: katarina.jasencakova@fri.uniza.sk (Katarína Jasenčáková), robert.jajcay@fmph.uniba.sk
(Robert Jajcay), pisanski@upr.si (Tomaž Pisanski)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 2590-9770
The Art of Discrete and Applied Mathematics 3 (2020) #P1.04
https://doi.org/10.26493/2590-9770.1279.02c
(Dostopno tudi na http://adam-journal.eu)
Nova posplošitev posplošenih Petersenovih
grafov*
Katarína Jasenčáková
Faculty of Management Science and Informatics, University of Žilina, Žilina, Slovakia
Robert Jajcay†
Faculty of Mathematics, Physics and Informatics, Comenius University, Bratislava,
Slovakia; povezan tudi s Fakulteto za matematiko, naravoslovje in informacijsko
tehnologijo, Univerza na Primorskem, Koper, Slovenija
Tomaž Pisanski‡
Fakulteta za matematiko, naravoslovje in informacijske tehnologije,
Univerza na Primorskem, Koper, Slovenija; povezan tudi s
FMF in IMFM, Univerza v Ljubljani, Jadranska 19, 1000 Ljubljana, Slovenija
Prejeto 30. novembra 2018, sprejeto 13. avgusta 2019, objavljeno na spletu 27. julija 2020
Povzetek
Obravnavamo novo družino kubičnih grafov, ki jo imenujemo grupno deljivi posplošeni
Petersenovi grafi (GDGP -grafi), in je, tako po definiciji kot po lastnostih, zelo podobna
družini posplošenih Petersenovih grafov. V članku se osredotočamo na določitev alge-
braičnih lastnosti grafov naše nove družine. Iščemo visoko simetrične grafe, t.j. grafe z ve-
likimi grupami avtomorfizmov, in točkovno- ali ločno-tranzitivne grafe. Posebej, podamo
aritmetične pogoje za določitvene parametre, ki zagotavljajo, da so grafi s temi parametri
točkovno-tranzitivni ali Cayleyevi, in poiščemo primer ločno-tranzitivnega GDGP -grafa,
ki ni niti CQ graf Fenga in Wanga niti posplošeni Petersenov graf.
Ključne besede: Posplošeni Petersenov graf, ločno-tranzitiven graf, točkovno-tranzitiven graf, Cay-
leyjev graf, grupa avtomorfizmov.
Math. Subj. Class.: 05C25
*Zahvaljujemo se neznanemu recenzentu za vse koristne in pronicljive komentarje.
†Avtor priznava podporo s strani projektov VEGA 1/0596/17, VEGA 1/0719/18, VEGA 1/0423/20, APVV-
15-0220, in od Javne agencije za raziskovalno dejavnost Republike Slovenije (raziskovalni projekti N1-0038,
N1-0062, J1-9108).
‡To delo je delno podprto s strani Javne agencije za raziskovalno dejavnost Republike Slovenije (razisko-
valni program P1-0294 in raziskovalni projekti N1-0032, J1-9187, J1-1690, N1-0140), ter delno s strani H2020
Teaming InnoRenew CoE.
E-poštni naslovi: katarina.jasencakova@fri.uniza.sk (Katarína Jasenčáková), robert.jajcay@fmph.uniba.sk
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/
(Robert Jajcay), pisanski@upr.si (Tomaž Pisanski)