On vertex-transitive graphs of odd prime-power order (Q1598831)

In [Ars Comb. 16-B, 297-302 (1983; Zbl 0535.05034)] \textit{D. Marušič} asked for a determination of the set NC of natural numbers \(n\), i.e. those numbers for which there exists a vertex-transitive graph on vertices which is not a Cayley graph. The question of membership of NC has been settled for all natural numbers which are not square-free (in view of the works of \textit{B. D. McKay} and \textit{C. E. Praeger} [see J. Aust. Math. Soc., Ser. A 56, No. 1, 53-63 (1994; Zbl 0795.05070) and J. Graph Theory 22, No. 4, 321-334 (1996; Zbl 0864.05041)]), and for all natural numbers which are products of two distinct primes (drawing together work by \textit{D. Marušič} and \textit{R. Scapellato} [see J. Graph Theory 16, No. 4, 375-387 (1992; Zbl 0764.05035), J. Comb. Theory, Ser. B 58, No. 1, 46-57 (1993; Zbl 0733.05047) and Combinatorica 14, No. 2, 187-201 (1994; Zbl 0799.05027)], by \textit{C. E. Praeger} et al. [see J. Comb. Theory, Ser. B 58, No. 2, 299-318 (1993; Zbl 0793.05071), J. Comb. Theory, Ser. B 59, No. 2, 245-266 (1993; Zbl 0793.05072)] and \textit{R. Wang} and \textit{M. Xu} [J. Comb. Theory, Ser. B 58, No. 2, 197-216 (1993; Zbl 0793.05074)]). More recently, an important contribution towards a complete classification of non-Cayley numbers of order a product of three distinct primes was made in [J. Comb. Math. Comb. Comput. 28, 187-213 (1998; Zbl 0917.05035), J. Algebr. Comb. 3, No. 1, 77-111 (1994; Zbl 0794.05046) and Discrete Math. 182, No. 1-3, 279-292 (1998; Zbl 0908.05050)]. In the paper under review the author proposes to study the following refinement of the above problem: Given a non-Cayley number \(n\), find the smallest valency \(d(n)\) of all non-Cayley graphs on \(n\) vertices. Then, as the main result of the paper, it is proved that if \(p\) is an odd prime and \(k\) a positive integer, then a vertex-transitive graph of order \(p^k\) with valency less than \(2p+2\) is a Cayley graph. It is remarked that, if \(p=2\), the latter result is not true as there is a 4-valent non-Cayley vertex transitive graph of order 16; see \textit{B. D. McKay} and \textit{G. F. Royle} [Ars Comb. 30, 161-176 (1990; Zbl 0805.05037)].