A conjecture on determining which $(n,k)$-star graphs are not Cayley graphs

Karimah Sweet, Li Li, Eddie Cheng, László Lipták, Daniel E. Steffy

Published 2017-03-17Version 1

In this paper, we continue the work begun by Cheng et al.~on classifying which of the $(n,k)$-star graphs are Cayley. We present a conjecture for the complete classification, and prove an asymptotic version of the conjecture, that is, the conjecture is true for all $k\geq 2$ when $n$ is sufficiently large. For $k=2,\dots,15$ we prove that the conjecture is true for all $n\geq k+2$ (with the possible exception of $S_{17,14}$). The proof reveals some unexpected connection between $(n,k)$-star graphs and the classification of multiply transitive groups (which is closely related to the classification of finite simple groups).