A line graph 
(also called an adjoint, conjugate, covering, derivative, derived, edge, edge-to-vertex
dual, interchange, representative, or 
-obrazom graph) of a simple
graph 
is obtained by associating a vertex with each edge of the graph and connecting two
vertices with an edge iff the corresponding edges of 
have a vertex in common (Gross and Yellen
2006, p. 20).
Given a line graph 
,
the underlying graph 
is known as the root graph of 
. The root graph of a simple
line graph is unique, except for the case 
(Harary 1994, pp. 72-73).
The line graph of a directed graph 
is the directed graph 
whose vertex
set corresponds to the arc set of 
and having an arc directed from
an edge 
to an edge 
if in 
, the head of 
meets the tail of 
(Gross and Yellen 2006, p. 265).
Line graphs are implemented in the Wolfram Language as LineGraph[g]. Precomputed line graph identifications of many named graphs can be obtained in the Wolfram Language using GraphData[graph, "LineGraphName"].
The numbers of simple line graphs on 
, 2, ... vertices are 1, 2, 4, 10, 24, 63, 166, 471, 1408,
... (OEIS A132220), and the numbers of connected
simple line graphs are 1, 1, 2, 5, 12, 30, 79, 227, ... (OEIS A003089).
The following table summarizes some named graphs and their corresponding line graphs.
Line graphs are claw-free.
The line graph of a graph with 
nodes, 
edges, and vertex degrees 
contains 
nodes and
 |
edges (Skiena 1990, p. 137). The incidence matrix 
of a graph and adjacency
matrix 
of its line graph are related by
 |
where 
is the identity
matrix (Skiena 1990, p. 136).
Krausz (1943) proved that a solution 
exists for a simple graph 
iff 
decomposes into complete subgraphs with each vertex of 
appearing in at most two members of
the decomposition. This theorem, however, is not useful for implementation of an
efficient algorithm because of the possibly large number of decompositions involved
(West 2000, p. 280).
van Rooij and Wilf (1965) shows that a solution to 
exists for a simple graph 
iff 
is claw-free and no induced
diamond graph of 
has two odd triangles. Here, a triangular subgraph 
is said to be even if the neighborhood 
and vertex set 
intersect in an odd number of points for some 
and even if 
and 
intersect in an even number of points for every 
(West 2000, p. 281).
A simple graph is a line graph of some simple graph iff if does not contain any of the above nine Beineke graphs as a forbidden
induced subgraph (van Rooij and Wilf 1965; Beineke 1968; Skiena 1990, p. 138;
Harary 1994, pp. 74-75; West 2000, p. 282; Gross and Yellen 2006, p. 405).
This statement is sometimes known as the Beineke theorem. These nine graphs are implemented
in the Wolfram Language as GraphData["Beineke"].
Of the nine, one has four nodes (the claw graph = star graph 
= complete bipartite
graph 
),
two have five nodes, and six have six nodes (including the wheel
graph 
).
A graph with minimum vertex degree at least 5 is a line graph iff it does not contain any of the above six Metelsky graphs as an induced subgraph (Metelsky and Tyshkevich 1997). These six graphs are implemented in the Wolfram Language as GraphData["Metelsky"].
A graph is not a line graph if the smallest element of its graph spectrum is less than 
(Van Mieghem, 2010, Liu et al. 2010).
Whitney (1932) showed that, with the exception of 
and 
, any two connected graphs
with isomorphic line graphs are isomorphic (Skiena 1990, p. 138).
Lehot (1974) gave a linear time algorithm that reconstructs the original graph from its line graph. Liu et al. (2010) give an 
algorithm for reconstructing the original graph from
its line graph, where 
is the number of vertices in the line graph. This algorithm is more time efficient
than the efficient algorithm of Roussopoulos (1973).
The line graph of an Eulerian graph is both Eulerian and Hamiltonian (Skiena 1990, p. 138). More information about cycles of line graphs is given by Harary and Nash-Williams (1965) and Chartrand (1968).
Taking the line graph twice does not return the original graph unless the line graph of a graph 
is isomorphic to 
itself. In fact, The only connected graph that
is isomorphic to its line graph is a cycle graph 
for 
(Skiena 1990, p. 137). Graph unions of cycle graphs
(e.g., 
,
, etc.) are also isomorphic to
their line graphs, so the graphs that are isomorphic to their line graphs are the
regular graphs of degree 2, and the total numbers of not-necessarily connected simple
graphs that are isomorphic to their lines graphs are given by the number of partitions
of their vertex count having smallest part 
, given for 
, 2, ... by 0, 0, 1, 1, 1, 2, 2, 3, 4, 5, 6, 9, 10, 13, 17,
... (OEIS A026796), the first few of which
are illustrated above.
Algorithm for Determining the Graph 
From Its Line Graph 
." Info. Proc. Let. 2, 108-112, 1973.Saaty,
T. L. and Kainen, P. C. "Line Graphs." §4-3 in 
Algorithm for Determining the Graph 
from its Line Graph 
." Inform. Proc. Lett. 2, 108-112, 1973.West,
D. B. "Characterizing Line Graphs."