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 automo...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.展开更多
基金supported by National Natural Science Foundation of China(Grant Nos.11171020,11231008 and 11271012)National Research Foundation of Korea(Grant No. K20110030452)
文摘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.
