Which merged Johnson graphs are Cayley graphs?
University of Southampton
Comenius University, Bratislava, and University of Primorska
Minisymposium: STRUCTURE AND PROPERTIES OF VERTEX-TRANSITIVE GRAPHS
Content: It has been conjectured that `most' vertex-transitive connected graphs are Cayley graphs. Recently Dobson and Malni\v c, building on earlier work of Godsil on Kneser graphs and of Kantor on permutation groups, have determined which Johnson graphs $J(n,k)$ are Cayley graphs: most are not, although they are all vertex-transitive and connected. Using finite group theory we extend this result to the distance $i$ Johnson graphs $J(n,k)_i$ and the merged Johnson graphs $J(n,k)_I$: despite some of these having much larger automorphism groups, no further Cayley graphs arise, apart from a few trivial examples. Indeed, in most cases the only vertex-transitive groups of automorphisms are the alternating and symmetric groups of degree $n$.