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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.