In graph theory, the line graph L(G) of undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by Harary & Norman (1960) although both Whitney (1932) and Krausz (1943) used the construction before this (Hemminger & Beineke 1978, p. 273). Other terms used for the line graph include the theta-obrazom, the covering graph, the derivative, the edge-to-vertex dual, the conjugate, and the representative graph (Hemminger & Beineke 1978, p. 273), as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph (Balakrishnan 1997, p. 44).
One of the earliest and most important theorems about line graphs is due to Hassler Whitney (1932), who proved that with one exceptional case the structure of G can be recovered completely from its line graph. In other words, with that one exception, the entire graph can be deduced from knowing the adjacencies of edges ("lines").
Read more about Line Graph: Formal Definition, Properties, Characterization and Recognition, Iterating The Line Graph Operator, Relations To Other Families of Graphs
Famous quotes containing the words line and/or graph:
“What comes over a man, is it soul or mind
That to no limits and bounds he can stay confined?
You would say his ambition was to extend the reach
Clear to the Arctic of every living kind.
Why is his nature forever so hard to teach
That though there is no fixed line between wrong and right,
There are roughly zones whose laws must be obeyed?”
—Robert Frost (1874–1963)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)