Non-Cayley vertex-transitive graphs of order twice the product of two odd primes

Miller, Alice Ann ; Praeger, Cheryl E.

Journal of Algebraic Combinatorics, Tome 3 (1994) no. 1, pp. 77-111.

Résumé

Summary: For a positive integer $n$, does there exist a vertex-transitive graph $Gamma$ on $n$ vertices which is not a Cayley graph, or, equivalently, a graph $Gamma$ on $n$ vertices such that Aut $Gamma$ 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 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 $pequiv$ 1 (mod $q$). Further, if $pnequiv$ 1 (mod $q), pequivqequiv$ 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.

Détail

Keywords: finite vertex-transitive graph, automorphism group of graph, non-Cayley graph, imprimitive permutation group