# line graph

Let $G$ be a graph. The line graph of $G$ is denoted by $L(G)$ and is defined as follows. The vertices of $L(G)$ are the edges of $G$. Two vertices of $L(G)$ are connected by an edge if and only if the corresponding edges in $G$ form a path (which must be a directed path if $G$ is a digraph).

###### Example 1.

Let $G$ be the undirected graph on the vertex set $V(G)=\{a,b,c,d\}$ and edge set $E(G)=\{ab,bc,cd,bd\}$. Then the line graph $L(G)$ has vertex set $V(L(G))=\{ab,bc,cd,bd\}$. Since $ab$ and $bc$ are incident in $G$, they are connected by an edge in $L(G)$. We label this edge by the unique walk from $a$ to $c$ determined by these edges, namely $abc$. With this notation, the edge set is $E(L(G))=\{abc,abd,bcd,bdc,cbd\}$.

 $\xymatrix{&a\ar@{-}[d]^{ab}&&&ab\ar@{-}[dl]_{abc}\ar@{-}[dr]^{abd}&\\ &b\ar@{-}[dl]_{bc}\ar@{-}[dr]^{bd}&&bc\ar@{-}[rr]^{bcd}\ar@{-}[dr]_{cbd}&&bd% \ar@{-}[dl]^{bdc}\\ c\ar@{-}[rr]_{cd}&&d&&cd}$

Above we display the graphs $G$ (left) and $L(G)$ (right).

Part of the reason for interest in line graphs is the following observation:

###### Proposition.

If a graph is Eulerian, then its line graph is Hamiltonian.

This follows immediately from the fact that a sequence of incident edges in $G$ is a sequence of incident vertices in $L(G)$.

###### Example 2.

Let $B_{n}$ be the de Bruijn digraph on binary strings of length $n$. Then for $n\geq 2$, the next de Bruijn digraph can be obtained by taking the line graph of the previous one, that is, $B_{n+1}=L(B_{n})$.

Title line graph LineGraph 2013-03-22 16:24:15 2013-03-22 16:24:15 mps (409) mps (409) 4 mps (409) Definition msc 05C75 DeBruijnDigraph