Line graph
|
|
In graph theory, the line graph L(G) of a graph G is a graph such that
- each vertex of L(G) represents an edge of G; and
- any two vertices of L(G) are adjacent if and only if their corresponding edges are incident, meaning they share a common endvertex, in G.
A line graph L(G) can easily be constructed from any graph by
- . Create a vertex in L(G) for each edge of G
- . For each vertex in L(G), add an edge to all of its neighbors -- all the other vertices corresponding to edges in G that touch the vertex at either end of the edge in G.
Some graphs are not a line graph. For example, the graph
*
|
|
*--*--*
\ | /
\|/
*
is not a line graph of any other graph.
The line graph of the above graph is
*
/|\
/ | \
*--|--*
|\ | /|
| \|/ |
| * |
| / \ |
|/ \|
*-----*
Properties
- The line graph of a connected graph is connected
- <math>\chi_E(G) = \chi_V(L(G))<math>, the edge chromatic number of a graph is equal to the vertex chromatic number of its line graphde:Kantengraph