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

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\ge 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
Canonical name	LineGraph
Date of creation	2013-03-22 16:24:15
Last modified on	2013-03-22 16:24:15
Owner	mps (409)
Last modified by	mps (409)
Numerical id	4
Author	mps (409)
Entry type	Definition
Classification	msc 05C75
Related topic	DeBruijnDigraph