Line graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of. is constructed in the following way: for each edge in, make a vertex in ; for every two edges in that have a vertex in common, make an edge between their corresponding vertices in .
The name line graph comes from a paper by although both and 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.
proved that with one exceptional case the structure of a connected graph 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, its line graph is a graph such that- each vertex of represents an edge of ; and
- two vertices of are adjacent if and only if their corresponding edges share a common endpoint in.
Example
The following figures show a graph and its line graph. 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 and 4,3.Properties
Translated properties of the underlying graph
Properties of a graph that depend only on adjacency between edges may be translated into equivalent properties in that depend on adjacency between vertices. For instance, a matching in is a set of edges no two of which are adjacent, and corresponds to a set of vertices in no two of which are adjacent, that is, an independent set.Thus,
- The line graph of a connected graph is connected. If is connected, it contains a path connecting any two of its edges, which translates into a path in containing any two of the vertices of. However, a graph 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 with vertices and edges, the number of vertices of the line graph is, and the number of edges of is half the sum of the squares of the degrees of the vertices in, minus.
- An independent set in corresponds to a matching in. In particular, a maximum independent set in corresponds to maximum matching in. 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 corresponds to a rainbow matching in.
- The edge chromatic number of a graph is equal to the vertex chromatic number of its line graph.
- The line graph of an edge-transitive graph is vertex-transitive. This property can be used to generate families of graphs that are vertex-transitive but are not Cayley graphs: if is an edge-transitive graph that has at least five vertices, is not bipartite, and has odd vertex degrees, then is a vertex-transitive non-Cayley graph.
- If a graph has an Euler cycle, that is, if is connected and has an even number of edges at each vertex, then the line graph of 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 is itself Hamiltonian, regardless of whether 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 and the shape of its degree distribution. 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
As well as and, there are some other exceptional small graphs with the property that their line graph has a higher degree of symmetry than the graph itself. For instance, the diamond graph has four graph automorphisms but its line graph has eight. In the illustration of the diamond graph shown, rotating the graph by 90 degrees is not a symmetry of the graph, but is a symmetry of its line graph. However, all such exceptional cases have at most four vertices. A strengthened version of the Whitney isomorphism theorem states that, for connected graphs with more than four vertices, there is a one-to-one correspondence between isomorphisms of the graphs and isomorphisms of their line graphs.
Analogues of the Whitney isomorphism theorem have been proven for the line graphs of multigraphs, but are more complicated in this case.
Strongly regular and perfect line graphs
The line graph of the complete graph is also known as the triangular graph, the Johnson graph, or the complement of the Kneser graph. Triangular graphs are characterized by their spectra, except for. They may also be characterized as the strongly regular graphs with parameters. The three strongly regular graphs with the same parameters and spectrum as are the Chang graphs, which may be obtained by graph switching from.The line graph of a bipartite graph is perfect, but need not be bipartite as the example of the claw graph shows. The line graphs of bipartite graphs form one of the key building blocks of perfect graphs, used in the proof of the strong perfect graph theorem. A special case of these graphs are the rook's graphs, line graphs of complete bipartite graphs. Like the line graphs of complete graphs, they can be characterized with one exception by their numbers of vertices, numbers of edges, and number of shared neighbors for adjacent and non-adjacent points. The one exceptional case is, which shares its parameters with the Shrikhande graph. When both sides of the bipartition have the same number of vertices, these graphs are again strongly regular. It has been shown that, except for , , and , all connected strongly regular graphs can be made non-strongly regular within two line graph transformations. The extension to disconnected graphs would require that the graph is not a disjoint union of .
More generally, a graph is said to be a line perfect graph if is a perfect graph. The line perfect graphs are exactly the graphs that do not contain a simple cycle of odd length greater than three. Equivalently, a graph is line perfect if and only if each of its biconnected components is either bipartite or of the form or . Every line perfect graph is itself perfect.
Other related graph families
All line graphs are claw-free graphs, graphs without an induced subgraph in the form of a three-leaf tree. As with claw-free graphs more generally, every connected line graph with an even number of edges has a perfect matching; equivalently, this means that if the underlying graph has an even number of edges, its edges can be partitioned into two-edge paths.The line graphs of trees are exactly the claw-free block graphs. These graphs have been used to solve a problem in extremal graph theory, of constructing a graph with a given number of edges and vertices whose largest tree induced as a subgraph is as small as possible.
All eigenvalues of the adjacency matrix of a line graph are at least −2. The reason for this is that can be written as, where is the signless incidence matrix of the pre-line graph and is the identity. In particular, is the Gramian matrix of a system of vectors: all graphs with this property have been called generalized line graphs.
Characterization and recognition
Clique partition
For an arbitrary graph, and an arbitrary vertex in, the set of edges incident to corresponds to a clique in the line graph. The cliques formed in this way partition the edges of. Each vertex of belongs to exactly two of them.The existence of such a partition into cliques can be used to characterize the line graphs: A graph is the line graph of some other graph or multigraph if and only if it is possible to find a collection of cliques in that partition the edges of, such that each vertex of belongs to exactly two of the cliques. It is the line graph of a graph if this set of cliques satisfies the additional condition that no two vertices of are both in the same two cliques. Given such a family of cliques, the underlying graph for which is the line graph can be recovered by making one vertex in for each clique, and an edge in for each vertex in with its endpoints being the two cliques containing the vertex in. By the strong version of Whitney's isomorphism theorem, if the underlying graph has more than four vertices, there can be only one partition of this type.
For example, this characterization can be used to show that the following graph is not a line graph:
In this example, the edges going upward, to the left, and to the right from the central degree-four vertex do not have any cliques in common. Therefore, any partition of the graph's edges into cliques would have to have at least one clique for each of these three edges, and these three cliques would all intersect in that central vertex, violating the requirement that each vertex appear in exactly two cliques. Thus, the graph shown is not a line graph.