arXiv Analytics

arXiv:1703.06111 [math.CO]AbstractReferencesReviewsResources

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

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).

Categories: math.CO, math.GR
Subjects: 05C25, 20D05
Related articles: Most relevant | Search more
arXiv:0711.3057 [math.CO] (Published 2007-11-20)
Cayley graphs formed by conjugate generating sets of S_n
arXiv:1507.05052 [math.CO] (Published 2015-07-16)
On the power graphs which are Cayley graphs of some groups
arXiv:1505.05771 [math.CO] (Published 2015-05-21)
Cayley graphs of more than one abelian group