Complement graph

Complement graph
The Petersen graph (on the left) and its complement graph (on the right).

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. It is not, however, the set complement of the graph; only the edges are complemented.

Formal construction

Let G = (VE) be a simple graph and let K consist of all 2-element subsets of V. Then H = (VK \ E) is the complement of G.

Applications and examples

Several graph-theoretic concepts are related to each other via complement graphs:

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Complement (mathematics) — Complement has a variety of uses in mathematics:* complement, an operation that transforms an integer into its additive inverse, useful for subtracting numbers when only addition is possible, or is easier * complement, a system for working with… …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Complement — In many different fields, the complement of X is something that together with X makes a complete whole something that supplies what X lacks. Complement may refer to: Complement (linguistics), a word or phrase having a particular syntactic role… …   Wikipedia

  • Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   Wikipedia

  • Graph embedding — In topological graph theory, an embedding of a graph G on a surface Sigma; is a representation of G on Sigma; in which points of Sigma; are associated to vertices and simple arcs (homeomorphic images of [0,1] ) are associated to edges in such a… …   Wikipedia

  • graph antihole — noun The complement of a graph hole …   Wiktionary

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • Colin de Verdière graph invariant — Colin de Verdière s invariant is a graph parameter μ(G) for any graph G introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.[1] Contents …   Wikipedia

  • Independent set (graph theory) — The nine blue vertices form a maximum independent set for the Generalized Petersen graph GP(12,4). In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices …   Wikipedia

  • Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”