Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration

A graph is called a semiregular graph if its automorphism group action on its ordered pair of adjacent vertices is semiregular. In this paper, a necessary and sufficient condition for an automorphism of the graph to be an automorphism of a map with the underlying graph is obtained. Using this result, all orientationpreserving automorphisms of maps on surfaces (orientable and nonorientable) or just orientable surfaces with a given underlying semiregular graph are determined. Formulas for the numbers of nonequivalent embeddings of this kind of graphs on surfaces (orientable, nonorientable or both) are established, and especially, the nonequivalent embeddings of circulant graphs of a prime order on orientable, nonorientable and general surfaces are enumerated.