Complement graph: Difference between revisions

Revision as of 00:25, 11 February 2016

Revision as of 00:32, 11 February 2016

Line 19:

| isbn=3-540-26182-6

}}. [http://diestel-graph-theory.com/index.html Electronic edition], page 4.</ref>

For [[directed graph]]s, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2-element [[ordered pair]]s of ''{{mvar|V''}} in place of the set ''{{mvar|K''}} in the formula above.

The complement is not defined for [[multigraph]]s. In graphs that allow [[loop (graph theory)|self-loops]] (but not multiple adjacencies) the complement of {{mvar|G}} may be defined by adding a self-loop to every vertex that does not have one in {{mvar|G}}, and otherwise using the same formula as above. This operation is, however, different from the one for simple graphs, since applying it to a graph with no self-loops would result in a graph with self-loops on all vertices.