Enumerating reflexible 2-cell embeddings of connected graphs

Abstract Two 2-cell embeddings l ： X → S and 3 ： X → S of a connected graph X into a closed orientable surface S are congruent if there are an orientation-preserving surface homeomorphism h on S and a graph automorphism γ of X such that γh = γj. A 2-cell embedding l ： X → S of a graph X into a closed orientable surface S is described combinatorially by a pair （X; p） called a map, where p is a product of disjoint cycle permutations each of which is the permutation of the darts of X initiated at the same vertex following the orientation of S. The mirror image of a map （X; p） is the map （X; p- 1）, and one of the corresponding embeddings is called the mirror image of the other. A 2-cell embedding of X is reflexible if it is congruent to its mirror image. Mull et al. [Proc Amer Math Soc, 1988, 103： 321-330] developed an approach for enumerating the congruence classes of 2-cell embeddings of graphs into closed orientable surfaces. In this paper we introduce a method for enumerating the congruence classes of reflexible 2-cell embeddings of graphs into closed orientable surfaces, and apply it to the complete graphs, the bouquets of circles, the dipoles and the wheel graphs to count their congruence classes of reflexible or nonreflexible （called chiral） embeddings.

Cubic semisymmetric graphs of order 8p^3

A regular edge-transitive graph is said to be semisymmetric if it is mot vertex-transitive. By Folkman [J. Combin. Theory 3 （1967）, 215-232], there is no semisymmetric graph of order 2p or 2p^2 for a prime p, and by Malni6 et al. [Discrete Math. 274 （2004）, 18-198], there exists a unique cubic semisymmetrie graph of order 2p3, the so called Gray graph of order 54. In this paper, it is shown that there is no connected cubic semisymmetric graph of order 4p^3 and that there exists a unique cubic semisymmetric graph of order 8p3, which is a Z2 × Z2-covering of the Gray graph.

Pentavalent symmetric graphs of order 2p^3

A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p^3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p^3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p^3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p^3 are all regular covers of the dipole Dip5 with covering transposition groups of order p^3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.

Cubic one-regular graphs of order twice a square-free integer

A graph is one-regular if its automorphism group acts regularly on the set of its arcs. Let n be a square-free integer. In this paper, we show that a cubic one-regular graph of order 2n exists if and only if n = 3 t p 1 p 2···p s ? 13, where t ? 1, s ? 1 and p i ’s are distinct primes such that 3| (p i ? 1). For such an integer n, there are 2 s?1 non-isomorphic cubic one-regular graphs of order 2n, which are all Cayley graphs on the dihedral group of order 2n. As a result, no cubic one-regular graphs of order 4 times an odd square-free integer exist.