Line Graph

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").