JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 19, No 2 (2004)

Shao-Fei Du , Jin Ho Kwak and Roman Nedela

Department of Mathematics, Capital Normal University, Beijing 100037, People's Republic of China

In this paper, we classify the regular embeddings of arc-transitive simple graphs of order pq for any two primes p and q (not necessarily distinct) into orientable surfaces. Our classification is obtained by direct analysis of the structure of arc-regular subgroups (with cyclic vertex-stabilizers) of the automorphism groups of such graphs. This work is independent of the classification of primitive permutation groups of degree p or degree pq for p q and it is also independent of the classification of the arc-transitive graphs of order pq for p q.

1. N.L. Biggs, “Classification of complete maps on orientable surfaces,” Rend. Mat. 4(6) (1971), 132-138.
2. N.L. Biggs and A.T. White, Permutation Groups and Combinatorial Structures, London Math. Soc. Lecture Notes 33, Cambridge University Press, Cambridge, 1979.
3. C.Y. Chao, “On the classification of symmetric graphs with a prime number of vertices,” Trans. Amer. Math. Soc. 158 (1971), 247-256.
4. L.E. Dickson, Linear Groups with an Exposition of the Galois Field Theory, Leipzig, 1901; Dover Publ. 1958.
5. S.F. Du, J.H. Kwak, and R. Nedela, “Regular embeddings of complete multipartite graphs,” to appear in Europ. J. Combinatorics.
6. W. Feit and J.G. Thompson, “Solvability of groups of odd order,” Pacific J. Math. 13 (1963), 775-1029.
7. A. Gardiner, R. Nedela, J. \check Sirá\check n, and M. \check Skoviera, “Characterization of graphs which underlie regular maps on closed surfaces,” J. London Math. Soc. 59 (1999), 100-108.
8. J.L. Gross and T.W. Tucker, Topological Graph Theory, Wiley, New York, 1987.
9. B. Huppert, Endliche Gruppen I, Springer-Verlag, Berlin, 1967.
10. B. Huppert and N. Blackburn, Finite Groups II, Springer-Verlag, New York, 1982.
11. L.D. James and G.A. Jones, “Regular orientable imbeddings of complete graphs,” J. Combin. Theory Ser. B 39 (1985), 353-367.
12. G.A. Jones, “Maps on surfaces and Galois groups,” Math. Slovaca 47 (1997), 1-33.
13. G. Jones and D. Singerman, “Theory of maps on orientable surfaces,” Proc. London Math. Soc. 37 (1978), 273-307.
14. G. Jones and D. Singerman, “Belyi functions, hypermaps and Galois groups,” Bull. London Math. Soc. 28 (1996), 561-590.
15. M.W. Liebeck and J. Saxl, “Primitive permutation groups containing an elements of large prime order,” J. London Math. Soc. 31 (1985), 237-249.
16. P. Lorimer, “Vertex-transitive graphs: Symmetric graphs of prime valency,” J. Graph Theory 8 (1984), 55-68.
17. D. Maru\check si\check c and R. Scapellato, “Characterizing vertex-transitive pq-graphs with an imprimitive automorphism subgroup,” J. Graph Theory 16 (1992), 375-387.
18. R. Nedela and M. \check Skoviera, “Exponents of orientable maps,” Proc. London Math. Soc. 75(3) (1997), 1-31.
19. R. Nedela and M. \check Skoviera, “Regular maps of canonical double coverings of graphs,” J. Combin. Theory Ser. B 67 (1996), 249-277.
20. C.E. Praeger, R.J. Wang, and M.Y. Xu, “Symmetric graphs of order a product of two distinct primes,” J. Combin. Theory Ser. B 58 (1993), 299-318.
21. C.E. Praeger and M.Y. Xu, “Vertex primitive transitive graphs of order a product of two distinct primes,” J. Combin. Theory Ser. B 59 (1993), 245-266.
22. R.J. Wang and M.Y. Xu, “A classification of symmetric graphs of order 3 p,” J. Combin. Theory Ser. B 58 (1993), 197-216.
23. M. Suzuki, Group Theory I, Springer- Verlag, New York, 1982.
24. M. \check Skoviera and J. \check Sirá\check n, “Regular maps from Cayley graphs. I: Balanced Cayley maps,” Discrete Math. 109 (1992), 265-276.
25. M. \check Skoviera and A. Zlato\check s, “Construction of regular maps with multiple edges,” in preparation.
26. S.E. Wilson, “Cantankerous maps and rotary embeddings of Kn,” J. Combin. Theory Ser. B 47 (1989), 262-273.
27. H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.