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:
“Michelangelo said to Pope Julius II, “Self negation is noble, self-culture is beneficent, self-possession is manly, but to the truly great and inspiring soul they are poor and tame compared to self-abuse.” Mr. Brown, here, in one of his latest and most graceful poems refers to it in an eloquent line which is destined to live to the end of time—”None know it but to love it, None name it but to praise.””
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)