Complement graph

As Komplementgraph complementary graph or complement is known in graph theory a special graph which is obtained from a given graph.

Here, the complementary graph has the same nodes as the origin graph, but differs in its edges: The Komplementgraph has exactly the edges, which has not the origin of the graph.

Definition

Be an undirected or directed graph without multiple edges. The undirected or directed graph without multiple edges is called Komplementgraph of, if the intersection of and is empty and the union of and

• In the undirected case, the set of all 2- element subsets of V or
• The directed case, the Cartesian product

Results.

The Komplementgraph a given graph is often referred to with. As a self-complementary graphs are called, which are isomorphic to its complementary graph.

Properties

• The complement of the complement of G is G itself

• Basic concept (graph theory )