Line Graphs and Circulants

Abstract

The line graph of $G$, denoted $L(G)$, is the graph with vertex set $E(G)$, where vertices $x$ and $y$ are adjacent in $L(G)$ if and only if edges $x$ and $y$ share a common vertex in $G$. In this paper, we determine all graphs $G$ for which $L(G)$ is a circulant graph. We will prove that if $L(G)$ is a circulant, then $G$ must be one of three graphs: the complete graph $K_4$, the cycle $C_n$, or the complete bipartite graph $K_{a,b}$, for some $a$ and $b$ with $gcd(a,b)=1$.