Which merged Johnson graphs are Cayley graphs?

Gareth Jones
University of Southampton

Robert Jajcay
Comenius University, Bratislava, and University of Primorska

PDF

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

Back to all abstracts