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

$$\text{xymatrix}\mathrm{\&}a\text{ar}\mathrm{@}-{[d]}^{ab}\mathrm{\&}\mathrm{\&}\mathrm{\&}ab\text{ar}\mathrm{@}-{[dl]}_{abc}\text{ar}\mathrm{@}-{[dr]}^{abd}\mathrm{\&}\mathrm{\&}b\text{ar}\mathrm{@}-{[dl]}_{bc}\text{ar}\mathrm{@}-{[dr]}^{bd}\mathrm{\&}\mathrm{\&}bc\text{ar}\mathrm{@}-{[rr]}^{bcd}\text{ar}\mathrm{@}-{[dr]}_{cbd}\mathrm{\&}\mathrm{\&}bd\text{ar}\mathrm{@}-{[dl]}^{bdc}c\text{ar}\mathrm{@}-{[rr]}_{cd}\mathrm{\&}\mathrm{\&}d\mathrm{\&}\mathrm{\&}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\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 |