Line graph

From Wikipedia, the free encyclopedia

In graph theory, the line graph L(G) of an undirected graph G is a graph such that

each vertex of L(G) represents an edge of G; and
any two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint in G.

That is, it is the intersection graph of the edges of G, representing each edge by the set of its two endpoints. Thus, properties of edges in graphs can be translated into properties about vertices in line graphs; for instance, the size of a maximum independent set in a line graph is the same as the size of a maximum matching in the original graph. 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 any connected graph can be recovered completely from its line graph.

A good introduction to line graphs is provided by Brandstädt et al. (1999).

1 Example
2 Properties
3 Characterization and recognition
4 Generalizations
5 References
6 External links
7 Headline text

[edit] Example

The following figures show a graph (left, with red 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 red 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 red graph) and 4,3 (corresponding to an edge sharing the endpoint 3 in the red graph).

[edit] Properties

Many of the following properties follow immediately from the standard way in which line graphs translate properties about edges in graphs to properties about vertices.

The line graph of a connected graph is connected.
The line graph of a bipartite graph is perfect (see König's theorem).
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.
Except for the case of $K 3$ and $K 1,3$ , if the line graphs of two connected graphs are isomorphic then the graphs are isomorphic (Whitney, 1932).
Every line graph is a claw-free 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.

[edit] Characterization and recognition

The nine minimal non-line graphs, from Beineke's forbidden-subgraph characterization of line graphs. A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.

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 exactly 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 Whitney (1932), 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. Roussopoulos (1973) 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 Beineke (1968, 1970). 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 it 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 K_1,3), shown on the top left of the illustration of forbidden subgraphs. Therefore, by Beineke's characterization, this example cannot be a line graph.

[edit] 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 K_1,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 (Zhang and Lin 1987).

[edit] References

Beineke, L. W. (1968). "Derived graphs of digraphs". H. Sachs, H.-J. Voss, and H.-J. Walter (Eds.) Beiträge zur Graphentheorie: 17–33, Leipzig: Teubner.

Beineke, L. W. (1970). "Characterizations of derived graphs". Journal of Combinatorial Theory 9: 129–135. MR 0262097.

Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999). Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. ISBN 0-89871-432-X.

Roussopoulos, N. D. (1973). "A max {m,n} algorithm for determining the graph H from its line graph G". Information Processing Letters 2 (4): 108–112. MR 0424435.