info prev up next book cdrom email home

Line Graph

\begin{figure}\begin{center}\BoxedEPSF{LineGraph.epsf scaled 800}\end{center}\end{figure}

A Line Graph $L(G)$ (also called an Interchange Graph) of a graph $G$ is obtained by associating a vertex with each edge of the graph and connecting two vertices with an edge Iff the corresponding edges of $G$ meet at one or both endpoints. In the three examples above, the original graphs are the Complete Graphs $K_3$, $K_4$, and $K_5$ shown in gray, and their line graphs are shown in black.


Saaty, T. L. and Kainen, P. C. ``Line Graphs.'' §4-3 in The Four-Color Problem: Assaults and Conquest. New York: Dover, pp. 108-112, 1986.

© 1996-9 Eric W. Weisstein