On quasi-Cayley graphs (Q1364780)

Given a quasigroup \(Q\) with a right identity element and a right-associative generating subset \(S\), a quasi-Cayley graph \(\text{QC}(Q,S)\) is constructed in very much the same way as a Cayley graph is constructed from a given group and a symmetric generating set. Since all Cayley graphs are quasi-Cayley and all quasi-Cayley graphs are vertex-transitive, quasi-Cayley graphs appear to be a useful concept allowing us to obtain a better understanding of vertex-transitive graphs. The article addresses the natural question of the existence of vertex-transitive graphs that are not quasi-Cayley and includes two infinite families of vertex-transitive non-quasi-Cayley graphs: the Kneser graphs \(K(2p+1,p)\) with \(p\) being an odd prime, and the Johnson graphs \(J(2p+1,p)\), \(p\) an odd prime, and \(J(n,2)\), \(n>5\) even. The proofs are based on a Sabidussi type characterization of quasi-Cayley graphs via the existence of a regular family of automorphisms combined with a nice counting argument involving rectangular arrays constructed from such regular families.