On non-Cayley vertex-transitive graphs of order a product of three primes (Q1850507)

In 1983, Marušič asked for a determination of the integers \(n\) for which there exists a vertex-transitive graph \(\Gamma\) on \(n\) vertices which is not a Cayley graph, that is, \(\Gamma\) admits no subgroup of automorphisms that is regular on vertices. Such integers \(n\) are called non-Cayley numbers. They possess the important, but elementary, property that every multiple of a non-Cayley number is itself a non-Cayley number, since if \(\Gamma\) is a non-Cayley vertex-transitive graph, then a vertex-disjoint union of any number of copies of \(\Gamma\) is also a non-Cayley vertex-transitive graph. Thus integers \(n\) with few divisors are of particular interest. Previous work of B. D. McKay and the second author determined completely the non-Cayley numbers that are not square-free. All vertex-transitive graphs with a prime number of vertices are Cayley-graphs, while the non-Cayley numbers of the form \(n= pq\), with \(p\), \(q\) distinct primes, were determined by Marušič and Scapellato. The purpose of this paper is to give necessary and sufficient conditions for a product of three distinct primes to be a non-Cayley number, thereby completing previous work of Hassani, Miller, Seress and the authors. The result sheds some light on the unresolved problem of whether there exist square-free non-Cayley numbers with an arbitrarily large number of prime divisors.