In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(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. Other terms used for the line graph include the covering graph, the derivative, the edge-to-vertex dual, the conjugate, the representative graph, and the θ-obrazom, as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph. Hassler Whitney (1932) proved that with one exceptional case the structure of a connected graph G can be recovered completely from its line graph. Many other properties of line graphs follow by translating the properties of the underlying graph from vertices into edges, and by Whitney's theorem the same translation can also be done in the other direction. Line graphs are claw-free, and the line graphs of bipartite graphs are perfect. Line graphs are characterized by nine forbidden subgraphs and can be recognized in linear time. Various extensions of the concept of a line graph have been studied, including line graphs of line graphs, line graphs of multigraphs, line graphs of hypergraphs, and line graphs of weighted graphs.
Formal definition Given a graph G, its line graph L(G) is a graph such that
each vertex of L(G) represents an edge of G; and two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint ("are incident") in G. That is, it is the intersection graph of the edges of G, representing each edge by the set of its two endpoints.
Example The following figures show a graph (left, with blue vertices) and its line graph (right, with green vertices). Each vertex of the line graph is shown labeled with the pair of endpoints of the corresponding edge in the original graph. For instance, the green vertex on the right labeled 1,3 corresponds to the edge on the left between the blue vertices 1 and 3. Green vertex 1,3 is adjacent to three other green vertices: 1,4 and 1,2 (corresponding to edges sharing the endpoint 1 in the blue graph) and 4,3 (corresponding to an edge sharing the endpoint 3 in the blue graph).
Properties
Translated properties of the underlying graph Properties of a graph G that depend only on adjacency between edges may be translated into equivalent properties in L(G) that depend on adjacency between vertices. For instance, a matching in G is a set of edges no two of which are adjacent, and corresponds to a set of vertices in L(G) no two of which are adjacent, that is, an independent set. Thus,
The line graph of a connected graph is connected. If G is connected, it contains a path connecting any two of its edges, which translates into a path in L(G) containing any two of the vertices of L(G). However, a graph G that has some isolated vertices, and is therefore disconnected, may nevertheless have a connected line graph. A line graph has an articulation point if and only if the underlying graph has a bridge for which neither endpoint has degree one. For a graph G with n vertices and m edges, the number of vertices of the line graph L(G) is m, and the number of edges of L(G) is half the sum of the squares of the degrees of the vertices in G, minus m. An independent set in L(G) corresponds to a matching in G. In particular, a maximum independent set in L(G) corresponds to maximum matching in G. Since maximum matchings may be found in polynomial time, so may the maximum independent sets of line graphs, despite the hardness of the maximum independent set problem for more general families of graphs. Similarly, a rainbow-independent set in L(G) corresponds to a rainbow matching in G. The edge chromatic number of a graph G is equal to the vertex chromatic number of its line graph L(G). The line graph of an edge-transitive graph is vertex-transitive. This property can be used to generate families of graphs that (like the Petersen graph) are vertex-transitive but are not Cayley graphs: if G is an edge-transitive graph that has at least five vertices, is not bipartite, and has odd vertex degrees, then L(G) is a vertex-transitive non-Cayley graph. If a graph G has an Euler cycle, that is, if G is connected and has an even number of edges at each vertex, then the line graph of G is Hamiltonian. However, not all Hamiltonian cycles in line graphs come from Euler cycles in this way; for instance, the line graph of a Hamiltonian graph G is itself Hamiltonian, regardless of whether G is also Eulerian. If two simple graphs are isomorphic then their line graphs are also isomorphic. The Whitney graph isomorphism theorem provides a converse to this for all but one pair of connected graphs. In the context of complex network theory, the line graph of a random network preserves many of the properties of the network such as the small-world property (the existence of short paths between all pairs of vertices) and the shape of its degree distribution. Evans & Lambiotte (2009) observe that any method for finding vertex clusters in a complex network can be applied to the line graph and used to cluster its edges instead.
Whitney isomorphism theorem
… excerpt ends here. Continue reading the full article.
