9
$\begingroup$

Let $n>3$ be an odd integer and let $K_n$ denote the complete graph on $n$ vertices. For which integers $n$ the line graph $L(K_n)$ is a Cayley graph? For even $n$, it follows from a result of Watkins that $L(K_n)$ is not a Cayley graph. For $n=5$, $L(K_n)$ is the complement of the Petersen graph and so it is not a Cayley graph.

$\endgroup$

1 Answer 1

13
$\begingroup$

If $L(K_n)$ is a Cayley graph for the group $G$, then $G$ is 2-homogeneous on $V(K_n)$, that is, it acts transitively on the set of unordered pairs of vertices of $K_n$. However it is not 2-transitive. Kantor "Automorphism groups of designs" determines the 2-homogeneous groups that are not 2-transitive. He finds that such groups exist if and only if $n$ is a prime power congruent to 3 mod 4, and therefore these are the only values of $n$ for which $L(K_n)$ is a Cayley graph.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .