Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
m Disambiguating links to Claw-free (link changed to Claw-free graph) using DisamAssist. |
||
Line 156:
For an arbitrary graph {{mvar|G}}, and an arbitrary vertex {{mvar|v}} in {{mvar|G}}, the set of edges incident to {{mvar|v}} corresponds to a [[Clique (graph theory)|clique]] in the line graph {{math|''L''(''G'')}}. The cliques formed in this way partition the edges of {{math|''L''(''G'')}}. Each vertex of {{math|''L''(''G'')}} belongs to exactly two of them (the two cliques corresponding to the two endpoints of the corresponding edge in {{mvar|G}}).
The existence of such a partition into cliques can be used to characterize the line graphs: A graph {{mvar|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 {{mvar|L}} (allowing some of the cliques to be single vertices) that partition the edges of {{mvar|L}}, such that each vertex of {{mvar|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 graph|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 {{mvar|L}} are both in the same two cliques. Given such a family of cliques, the underlying graph {{mvar|G}} for which {{mvar|L}} is the line graph can be recovered by making one vertex in {{mvar|G}} for each clique, and an edge in {{mvar|G}} for each vertex in {{mvar|L}} with its endpoints being the two cliques containing the vertex in {{mvar|L}}. By the strong version of Whitney's isomorphism theorem, if the underlying graph {{mvar|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:
| |||