JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 3, No 1 (1994)

Alice Ann Miller and Cheryl E. Praeger

For a positive integer n, does there exist a vertex-transitive graph on n vertices which is not a Cayley graph, or, equivalently, a graph on n vertices such that Aut is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2 pq, where 2 <> q <> p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2 pq vertices which are not Cayley graphs in the case where p 1 (mod q). Further, if p 1 (mod q), p q 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2 pq = 66, or every vertex-transitive graph of order 2 pq admitting a transitive imprimitive group of automorphisms is a Cayley graph.

1. B. Alspach and T.D. Parsons, "A construction for vertex-transitive graphs," Canad. J. Math. 34 (1982), 307-318.
2. B. Alspach and R.J. Sutcliffe, "Vertex-transitive graphs of order 2p," Ann. New York Acad. Sci. 319 (1979), 18-27.
3. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
4. P.J. Cameron, "Finite permutation groups and finite simple groups," Bull London Math. Soc. 13 (1981), 1-22.
5. P.J. Cameron, P.M. Neumann, and D.N. Teague, "On the degrees of primitive permutation groups," Math. Z. 180 (1982), 141-149.
6. J.J. Cannon, "An introduction to the group theory language Cayley," in (Atkinson, M., ed.), Computational Group Theory (Proc. of LMS Meeting, Durham) Academic Press, 1982, pp. 145-183.
7. J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, and R.A. Wilson, Atlas of Finite Groups, (Clarendon Press, Oxford, England, 1985).
8. B.N. Cooperstein, "Minimal degree for a permutation representation of a classical group," Israel J. Math. 30 (1978), 213-235.
9. L.E. Dickson, Linear Groups with an Exposition of the Galois Field Theory, Dover, New York, 1958.
10. R. Frucht, J. Graver, and M.E. Watkins, "The groups of the generalized Petersen graphs," Proc. Cam. Phil. Soc. 70 (1971), 211-218.
11. D. Gorenstein, Finite Groups, Harper and Row, New York, 1968.
12. D. Gorenstein and R. Lyons, "The local structure of finite groups of characteristic 2 type," Mem. Amer. Math. Soc. 42 (276), p. 72, 1983.
13. R. Guralnick, "Subgroups of prime power index in a simple group," J. Alg. 81 (1983), 304-311.
14. M.W. Liebeck, "The affine permutation groups of rank three," Proc. London Math. Soc. 54 (1987), 477-516.
15. M.W. Liebeck, C.E. Praeger, and J. Saxl, "A classification of the maximal subgroups of the finite alternating and symmetric groups," J. Alg. 111 (1987), 365-383.
16. M.W. Liebeck and J. Saxl, "Primitive permutation groups containing an element of large prime order," J. London Math Soc. (2) 31 (1985), 237-249.
17. B.D. McKay, "Transitive graphs with fewer than twenty vertices," Math. Comp. 33 (1979), 1101-1121, and a microfiche supplement. 18 B.D. McKay, "Nauty user's guide (version 1.5)," Technical report TR-CS-90-02, Computer Science Department, Australian National University, 1990.
19. B.D. McKay and C.E. Praeger, "Vertex-transitive graphs which are not Cayley graphs, I," J. Austral. Math. Soc.(A) to appear.
20. B.D. McKay and C.E. Praeger, "Vertex-transitive graphs which are not Cayley graphs, II," preprint (1992).
21. B.D. McKay and C.F. Royle, "The transitive graphs with at most 26 vertices," Ars Combinatoria to appear.
22. D. Marusic, "Cayley properties of vertex symmetric graphs," Ars Combin. 16B (1983), 297-302.
23. D. Marusic, "Vertex-transitive graphs and digraphs of order pk," Ann. of Disc. Math. 27 (1985), 115-128.
24. D. Marusic and R. Scapellato, "Characterising vertex-transitive pq-graphs with an imprimitive automorphism group," J. Graph Theory, 16 (1992), 375-387.
25. D. Marusic and R. Scapellato, "Imprimitive representations of SL(2, 2k)," J. Combin. Theory (B), to appear.
26. C.E. Praeger and M.Y. Xu, "Vertex-primitive graphs of order a product of two distinct primes," J. Combin. Theory (B), to appear.
27. G.F. Royle and C.E. Praeger, "Constructing the vertex-transitive graphs of order 24," /. Symbolic Comput. 8, (1989), 309-326.
28. M. Schonert, et. al., "GAP: Groups, Algorithms and Programming," Lehrstuhl D fur Mathematik, RWTH Aachen (1992).
29. L.H. Soicher, "GRAPE: a system for computing with graphs and groups," in Groups and Computation (eds. L. Finkelstein and W.M. Kantor) DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 11 Amer. Math. Soc., 1993, pp. 287-291.
30. D.E. Taylor, "Two-graphs and doubly transitive groups," J. Combin. Theory (A) 61 (1992), 113-122.
31. R.J. Wang and M.Y. Xu, "A classification of symmetric graphs of order 3p," J. Combin. Theory (B), 58 (1993), 197-216.
32. M.E. Watkins, "Vertex-transitive graphs which are not Cayley graphs," in Cycles and Rays (eds. G. Hahn et al.) Kluwer, Netherlands, 1990, pp. 243-256.
33. H. Wielandt, "Permutation groups through invariant relations and invariant functions," Lecture Notes, Ohio State University, Columbus, Ohio, 1969.