arXiv Analytics

Sign in

arXiv:1703.06111 [math.CO]AbstractReferencesReviewsResources

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

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:1701.08384 [math.CO] (Published 2017-01-29)
A characterization of 2-dimensional Cayley graphs on dihedral groups