line graph

Let G be a graph. The line graphMathworldPlanetmath 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 digraphMathworldPlanetmath).

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 incidentPlanetmathPlanetmathPlanetmath 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:


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 Bn be the de Bruijn digraph on binary strings of length n. Then for n2, the next de Bruijn digraph can be obtained by taking the line graph of the previous one, that is, Bn+1=L(Bn).

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