|
|
|
|
|
Let  be a graph. The line graph of  is denoted by  and is defined as follows. The vertices of  are the edges of  . Two vertices of  are connected by an edge if and only if the corresponding edges in  form a path (which must be a directed path if  is a digraph).
Example 1 Let  be the undirected graph on the vertex set
 and edge set
 . Then the line graph  has vertex set
 . Since  and  are incident in  , they are connected by an edge in  . We label this edge by the unique walk from  to  determined by these edges, namely  . With this notation, the edge set is
 .
Above we display the graphs  (left) and  (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  is a sequence of incident vertices in  .
|
Anyone with an account can edit this entry. Please help improve it!
"line graph" is owned by mps.
|
|
(view preamble)
Cross-references: length, strings, binary, de Bruijn digraph, sequence, Hamiltonian, walk, incident, digraph, path, edges, vertices, graph
This is version 1 of line graph, born on 2006-11-13.
Object id is 8552, canonical name is LineGraph.
Accessed 1724 times total.
Classification:
| AMS MSC: | 05C75 (Combinatorics :: Graph theory :: Structural characterization of types of graphs) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & a\ar@{-}[d]^{ab} & & & ab\ar@{... ...]_{cbd} & & bd\ar@{-}[dl]^{bdc} \ c\ar@{-}[rr]_{cd} & & d & & cd } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/8552/l2h/img22.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & a\ar@{-}[d]^{ab} & & & ab\ar@{... ...]_{cbd} & & bd\ar@{-}[dl]^{bdc} \ c\ar@{-}[rr]_{cd} & & d & & cd } } \end{xy}$")
