A new generalization of generalized Petersen graphs

  • Katarína Jasenčáková University of Žilina, Slovakia https://orcid.org/0000-0001-7615-0038
  • Robert Jajcay Comenius University, Slovakia, and University of Primorska, Slovenia
  • Tomaž Pisanski University of Primorska, Slovenia
Keywords: Generalised Petersen graph, arc-transitive graph, vertex-transitive graph, Cayley graph, automorphism group


We discuss a new family of cubic graphs, which we call group divisible generalized Petersen graphs (GDGP-graphs), that bears a close resemblance to the family of generalized Petersen graphs; both in definition and properties. The focus of our paper is on determining 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 generalized Petersen graph. 


International Workshop on Symmetries of Graph and Networks 2018