Enumerating The Conjugacy Classes Of Digraph Embeddings

One important topic of topological graph theory is to count 2-cell embedding of a given graph in surfaces. While counting embeddings of graphs has become an often discussed topic in topological graph theory, there are few results on enumerating directed embeddings of digraphs. A digraph D is called an Eulerian digraph if in(v) = out(v) for each vertex v of D. 2-cell embedding of an Eulerian digraph D into a closed surface is said to be directed if the boundary of each face is a directed closed walk in D. The embeddings of Eulerian digraph was first studied by W. T. Tutte in his article [The dissection of equilateral triangles into equilateral triangles,Proc. Cambridge Philos. Soc.44(1948) 463-482]. An alternating rotation at a vertex v of a Eulerian digraph D is a cyclic ordering of all the arcs incident with v such that the in-arcs and out-arcs at v alternate. An alternating rotation system ? of a graph D indicates an assignment of an alternating rotation at every vertex of D. Two alternating rotation systems ?, ? ? R(D) are said to be equivalent if there is an automorphism ? ? Aut(D) such that ? = ?(?). The equivalent rotation system is in the same conjugacy class. In this paper, we mainly investigate enumerating of conjugacy classes of digraph as following:1. Enumerating the conjugacy classes of embeddings of an Eulerian digraph is discussed.2. As an application, we calculate the conjugacy classes of embeddings of directed bouquets of cycles Bnand directed dipoles OD2 nwhich are oriented by bouquets of cycles and dipoles respectively.3. Next, we study the conjugacy classes of embeddings of bi-directional bracelet BBnand uni-directional bracelet U Bnwhich derived from bracelet.4. There are many orientations of complete graph and complete bipartite graph. The explicit formulas for a class of regular tournaments T2n+1and one type of complete bipartite tournaments are given.5. At last, we study the asymptotic results for the conjugacy classes of embeddings of the four classes of digraphs.