{ "id": "1703.06111", "version": "v1", "published": "2017-03-17T17:22:17.000Z", "updated": "2017-03-17T17:22:17.000Z", "title": "A conjecture on determining which \$(n,k)\$-star graphs are not Cayley graphs", "authors": [ "Karimah Sweet", "Li Li", "Eddie Cheng", "László Lipták", "Daniel E. Steffy" ], "categories": [ "math.CO", "math.GR" ], "abstract": "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).", "revisions": [ { "version": "v1", "updated": "2017-03-17T17:22:17.000Z" } ], "analyses": { "subjects": [ "05C25", "20D05" ], "keywords": [ "star graphs", "conjecture", "cayley graphs", "finite simple groups", "work begun" ], "note": { "typesetting": "TeX", "pages": 0, "language": "en", "license": "arXiv", "status": "editable" } } }