PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
line graph (Definition)

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



Anyone with an account can edit this entry. Please help improve it!

"line graph" is owned by mps.
(view preamble)

View style:

See Also: de Bruijn digraph

Log in to rate this entry.
(view current ratings)

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 MSC05C75 (Combinatorics :: Graph theory :: Structural characterization of types of graphs)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)