ENUMERATION OF GRAPH EMBEDDINGS

Abstract

For a finite connected simple graph G, let Gamma be a group of graph automorphisms of G. Two 2-cell embeddings l:G --> S and j: G --> S of a graph G into a closed surface S (orientable or nonorientable) are congruent with respect to Gamma if there are a surface homeomorphism h:S --> S and a graph automorphism gamma epsilon Gamma such that h circle l=j circle gamma. In this paper, we give an algebraic characterization of congruent 2-cell embeddings, from which we enumerate the congruence classes of 2-cell embeddings of a graph G into closed surfaces with respect to a group of automorphisms of G, not just the full automorphism group. Some applications to complete graphs are also discussed. As an orientable case, the oriented congruence of a graph G into orientable surfaces with respect to the full automorphism group of G was enumerated by Mull et al. (1988).