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 exactly two of the cliques. In order to do this, it may be necessary for some of the cliques to be single vertices. By Whitney's theorem (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. Therefore, except for the case of and, if the line graphs of two connected graphs are isomorphic then the graphs are isomorphic. 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 (1970) (and reported earlier without proof by Beineke (1968)). 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 (Metelsky & Tyshkevich 1997). This result is similar to the results of Line graphs of hypergraphs.
Read more about this topic: Line Graph
Famous quotes containing the word recognition:
“Justice begins with the recognition of the necessity of sharing. The oldest law is that which regulates it, and this is still the most important law today and, as such, has remained the basic concern of all movements which have at heart the community of human activities and of human existence in general.”
—Elias Canetti (b. 1905)