|
|
|
|
Line graph
|
| |
|
| |
In a graph theory, the line graph L(G) of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The line graph is also sometimes called the edge graph, the adjoint graph, the interchange graph, or the derived graph of G.
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.
Discussion
Ask a question about 'Line graph' Start a new discussion about 'Line graph' Answer questions from other users |
Encyclopedia
In a graph theory, the line graph L(G) of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The line graph is also sometimes called the edge graph, the adjoint graph, the interchange graph, or the derived graph of G.
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").
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 adjacent") in G.
That is, it is the intersection graph of the edges of G, representing each edge by the set of its two endpoints.
Examples
Example construction
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).
Image:Line graph construction 1.svg|Graph G
Image:Line graph construction 2.svg|Vertices in L(G) constructed from edges in G
Image:Line graph construction 3.svg|Added edges in L(G)
Image:Line graph construction 4.svg|The line graph L(G)
Line graphs of convex polyhedra
A source of examples from geometry are the line graphs of the graphs of convex polyhedra. Taking the line graph of the graph of the tetrahedron one gets the graph of the octahedron; from both the graph of the cube and the octahedron one gets the graph of a cuboctahedron; from both
the graph of the dodecahedron and the icosahedron one gets the graph of the icosidodecahedron, etc. Geometrically, the operation consists in cutting each vertex of the polyhedron with a plane cutting all edges adjacent to the vertex at their midpoints; it is sometimes named rectification.
Properties
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 maximum independent set in a line graph corresponds to maximum matching in the original graph. 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.
- 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.
- 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.)
- Line graphs are claw-free graphs, graphs without an induced subgraph in the form of a three-leaf tree.
Characterization and recognition
A graph G is the line graph of some other graph, if and only if it is possible to find a collection of cliques in G, partitioning the edges of G, such that each vertex of G belongs to at most two of the cliques. In order to do this, it may be necessary for some of the cliques to be single vertices. By the result of (see also ), if G is not a triangle, there can be only one partition of this type. If such a partition exists, we can recover the original graph for which G is a line graph, by creating a vertex for each clique, and connecting two cliques by an edge whenever G contains a vertex belonging to both cliques. Therefore, except for the case of and , if the line graphs of two connected graphs are isomorphic then the graphs are isomorphic.
used this observation as the basis for a linear time algorithm for recognizing line graphs and reconstructing their original graphs.
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.
An alternative characterization of line graphs was proven by (see also ). He showed that there are nine minimal graphs that are not line graphs, such that any graph that is not a line graph has one of these nine graphs as an induced subgraph. That is, a graph is a line graph if and only if no subset of its vertices induces one of these nine graphs. In the example above, the four topmost vertices induce a claw (that is, a complete bipartite graph K1,3), shown on the top left of the illustration of forbidden subgraphs. Therefore, by Beineke's characterization, this example cannot be a line graph. For graphs with minimum degree at least 5, only the six subgraphs in the left and right columns of the figure are needed in the characterization . This result in Metelsky et al. is similar to the results of Line graphs of hypergraphs.
Iterating the line graph operator
consider the sequence of graphs
- G, L(G), L(L(G)), L(L(L(G))), ...
They show that, when G is a finite connected graph, only four possible behaviors are possible for this sequence:
- If G is a cycle graph then L(G) and each subsequent graph in this sequence is isomorphic to G itself. These are the only connected graphs for which L(G) is isomorphic to G.
- If G is a claw K1,3, then L(G) and all subsequent graphs in the sequence are triangles.
- If G is a path graph then each subsequent graph in the sequence is a shorter path until eventually the sequence terminates with an empty graph.
- In all remaining cases, the sizes of the graphs in this sequence eventually increase without bound.
If G is not connected, this classification applies separately to each component of G.
Relations to other families of graphs
Every line graph is a claw-free graph. Some of the properties of claw-free graphs are generalizations of those of line graphs.
The line graph of a bipartite graph is perfect (see König's theorem). The line graphs of bipartite graphs form one of the key building blocks of perfect graphs, used in the proof of the perfect graph theorem. A special case is the rook's graphs, line graphs of complete bipartite graphs.
Generalizations
The concept of the line graph of G may naturally be extended to the case where G is a multigraph, although in that case Whitney's uniqueness theorem no longer holds; for instance a complete bipartite graph K1,n has the same line graph as a graph in which two vertices are connected by an n-tuple edge.
It is also possible to generalize line graphs to directed graphs. If G is a directed graph, its directed line graph or line digraph has one vertex for each edge of G. Two vertices representing directed edges from u to v and from w to x in G are connected by an edge from uv to wx in the line digraph when v = w. That is, each edge in the line digraph of G represents a length-two directed path in G. The de Bruijn graphs may be formed by repeating this process of forming directed line graphs, starting from a complete directed graph .
The edges of a hypergraph may form an arbitrary family of sets, so the concept of the line graph of a hypergraph is defined as the intersection graph of the sets from the family.
External links
|
| |
|
|
