Content deleted Content added
m Reverted edits by 47.220.235.153 (talk) to last version by Wcherowi |
Dokidaki-ylc (talk | contribs) mNo edit summary |
||
Line 151:
For an arbitrary graph ''G'', and an arbitrary vertex ''v'' in ''G'', the set of edges incident to ''v'' corresponds to a [[Clique (graph theory)|clique]] in the line graph ''L''(''G''). The cliques formed in this way partition the edges of ''L''(''G''). Each vertex of ''L''(''G'') belongs to exactly two of them (the two cliques corresponding to the two endpoints of the corresponding edge in ''G'').
The existence of such a partition into cliques can be used to characterize the line graphs: A graph ''L'' is the line graph of some other graph or multigraph if and only if it is possible to find a collection of cliques in ''L'' (allowing some of the cliques to be single vertices) that partition the edges of ''L'', such that each vertex of ''L'' belongs to exactly two of the cliques.<ref name="h72-8.4">{{harvtxt|Harary|1972}}, Theorem 8.4, p. 74, gives three equivalent characterizations of line graphs: the partition of the edges into cliques, the property of being [[claw-free]] and odd [[Diamond graph|diamond]]-free, and the nine forbidden graphs of Beineke.</ref> It is the line graph of a graph (rather than a multigraph) if this set of cliques satisfies the additional condition that no two vertices of ''L'' are both in the same two cliques. Given such a family of cliques, the underlying graph ''G'' for which ''L'' is the line graph can be recovered by making one vertex in ''G'' for each clique, and an edge in ''G'' for each vertex in ''L'' with its endpoints being the two cliques containing the vertex in ''L''. By the strong version of Whitney's isomorphism theorem, if the underlying graph ''G'' has more than four vertices, there can be only one partition of this type.▼
▲A graph ''L'' is the line graph of some other graph or multigraph if and only if it is possible to find a collection of cliques in ''L'' (allowing some of the cliques to be single vertices) that partition the edges of ''L'', such that each vertex of ''L'' belongs to exactly two of the cliques.<ref name="h72-8.4">{{harvtxt|Harary|1972}}, Theorem 8.4, p. 74, gives three equivalent characterizations of line graphs: the partition of the edges into cliques, the property of being [[claw-free]] and odd [[Diamond graph|diamond]]-free, and the nine forbidden graphs of Beineke.</ref> It is the line graph of a graph (rather than a multigraph) if this set of cliques satisfies the additional condition that no two vertices of ''L'' are both in the same two cliques. Given such a family of cliques, the underlying graph ''G'' for which ''L'' is the line graph can be recovered by making one vertex in ''G'' for each clique, and an edge in ''G'' for each vertex in ''L'' with its endpoints being the two cliques containing the vertex in ''L''. By the strong version of Whitney's isomorphism theorem, if the underlying graph ''G'' 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:
Line 166 ⟶ 165:
The algorithms of {{harvtxt|Roussopoulos|1973}} and {{harvtxt|Lehot|1974}} are based on characterizations of line graphs involving odd triangles (triangles in the line graph with the property that there exists another vertex adjacent to an odd number of triangle vertices). However, the algorithm of {{harvtxt|Degiorgi|Simon|1995}} uses only Whitney's isomorphism theorem. It is complicated by the need to recognize deletions that cause the remaining graph to become a line graph, but when specialized to the static recognition problem only insertions need to be performed, and the algorithm performs the following steps:
*Construct the input graph ''L'' by adding vertices one at a time, at each step choosing a vertex to add that is adjacent to at least one previously-added vertex. While adding vertices to ''L'', maintain a graph ''G'' for which ''L''
*When adding a vertex ''v'' to a graph ''L''(''G'') for which ''G'' has four or fewer vertices, it might be the case that the line graph representation is not unique. But in this case, the augmented graph is small enough that a representation of it as a line graph can be found by a [[brute force search]] in constant time.
*When adding a vertex ''v'' to a larger graph ''L'' that equals the line graph of another graph ''G'', let ''S'' be the subgraph of ''G'' formed by the edges that correspond to the neighbors of ''v'' in ''L''. Check that ''S'' has a [[vertex cover]] consisting of one vertex or two non-adjacent vertices. If there are two vertices in the cover, augment ''G'' by adding an edge (corresponding to ''v'') that connects these two vertices. If there is only one vertex in the cover, then add a new vertex to ''G'', adjacent to this vertex.
Each step either takes constant time, or involves finding a vertex cover of constant size within a graph ''S'' whose size is proportional to the number of neighbors of
==Iterating the line graph operator==
| |||