Automorphisms of maps with a given underlying graph and their application to enumeration (Q2581145)

A graph is said to be semi-regular if the automorphism group action on the ordered pairs of adjacent vertices is semi-regular. The authors enumerate non-equivalent imbeddings of a semi-regular graph on orientable or nonnorientable surfaces, with particular attention to circulant graphs of prime order. Along the way, they show that, for any connected graph \(G\), an automorphism \(g\) in \(\text{Aut\,}G\) is an orientation-preserving automorphism of a map with underlying graph \(G\) if and only if \(g\) acts semi-regularly on the ordered pairs of adjacent vertices of \(G\).