Resolving the Hamiltonian problem for vertex-transitive graphs of order a product of two primes (Q2236659)

With only four connected vertex-transitive graphs known not to contain a Hamilton cycle, the classification of Hamiltonian vertex-transitive graphs is a widely studied problem that is in no way close to being resolved. Even partial results are therefore of great interest and the results obtained in this paper complete the classification of Hamiltonian vertex-transitive graphs whose orders are products of two primes. This is no small achievement obtained using a wide range of techniques from finite group theory, algebraic graph theory, number theory, and the theory of finite fields. \par The key class considered in this paper -- the only class left unclassified among all vertex-transitive graphs of order a product of two primes -- is the class of graphs satisfying the property that every vertex-transitive group of automorphisms of the graph acts primitively on its vertices. All such graphs are orbital graphs of one of seven classes of groups, and the Hamiltonicity of orbital graphs constructed from these groups is tested using theorems of \textit{V. Chvátal} [J. Comb. Theory, Ser. B 12, 163--168 (1972; Zbl 0213.50803)] and \textit{B. Jackson} [ibid. 29, 27--46 (1980; Zbl 0377.05027)]. The main breakthrough has been obtained by the same authors when, in their previous paper, they managed to show that all orbital graphs constructed from the two infinite classes on the list are Hamiltonian. Part of the present proof depends on a technique called the lifting cycle technique which has a surprising connection to the polycirculant conjecture (the conjecture that every vertex-transitive graph admits a semi-regular automorphism) which is known to be true for vertex-transitive graphs of order a product of two distinct primes. \par The classification completed in the paper confirms that the only connected vertex-transitive graph of order a product of two primes that is not Hamiltonian is the Petersen graph.