Graph isomorphic to its own line graph

Question

I know if $G$ is a connected graph $G$ with $n \ge 3 $ nodes, and $L(G)$ is the line graph of $G$, then

$$G \cong L(G) \iff G\;\text{is 2-regular}$$

Is this still true if we drop the condition that $G$ is connected or $n \ge 3$?

I am guessing NO but could not quite produce a counterexample.

Answer 1

If $n<3$, you cannot create a 2-regular graph, and all graph on 1 or 2 vertices are not isomorphic to their line graph. The only exception would be the empty graph.

Lets try to find a counterexample. Let $G$ be a disconnected graph.

Any finite 2-regular graph is a collection of cycles, hence verifying $G\cong L(G)$. Therefore the implication $\Leftarrow$ holds.

So for the $\Rightarrow$ implication, suppose that $G\cong L(G)$.

$G$ is disconnected. Each component create its own line component, and it is known that the cycle graph are the only connected graph isomorphic to their own line graph. Therefore if we want a disconnected graph isomorphic to its line graph we have to construct a graph with either

• 2 components, $C_1$ and $C_2$, where $L(C_1)=C_2$ and $L(C_2)=C_1$,
• or 3 components, $C_1$, $C_2$ and $C_3$, where $L(C_1)=C_2$, $L(C_2)=C_3$, $L(C_3)=C_1$
• $\ldots$

Written more generaly, we need to find a connected graph $C$ such that there is some $k\geq 2$ with $L^k(C)=C$. And $G$ will be the disjoint union of all $L^i(C)$ for $i=1,\ldots,k$.

The issue is that in here, van Rooij and Wilf prove that when $C$ is a finite connected graph, only four behaviors are possible for the sequence $C,L(C),L(L(C)),\ldots$:

1. If $C$ is a cycle graph then $L(C)$ and each subsequent graph in this sequence are isomorphic to $C$ itself
2. If $C$ is a claw $K_{1,3}$, then $L(C)$ and all subsequent graphs in the sequence are triangles.
3. If $C$ is a path graph then each subsequent graph in the sequence is a shorter path until eventually the sequence terminates with an empty graph.
4. In all remaining cases, the sizes of the graphs in this sequence increase without bound.

Therefore we can never find such a graph $C$! If your gaph is finite, the connected condition is not necessary.

Edit the cited paper is available here. note that the terminology Line was not yet used, and that the use the name interchange graph. Your question is the main theorem of this paper,

Theorem 1 : G = G" if and only if G is regular of degree 2.

Note that they do not require connectivity.