Complement graph: Difference between revisions

Revision as of 20:48, 16 May 2021

Latest revision as of 22:13, 23 June 2023

(5 intermediate revisions by 4 users not shown)

Line 1:

{{short description|Graph with same nodes but opposite connections as another}}

[[File:Petersen graph complement.svg|thumb|upright=1.35|The [[Petersen graph]] (on the left) and its complement graph (on the right).]]

In the [[mathematical]] field of [[graph theory]], the '''complement''' or '''inverse''' of a [[Graph (discrete mathematics)|graph]] {{mvar|G}} is a graph {{mvar|H}} on the same [[Vertex (graph theory)|vertices]] such that two distinct vertices of {{mvar|H}} are adjacent [[if and only if]] they are not adjacent in {{mvar|G}}. That is, to generate the complement of a graph, one fills in all the missing [[Edge (graph theory)|edges]] required to form a [[complete graph]], and removes all the edges that were previously there.<ref name="bm">{{citation

| last1=Bondy

| first1=John Adrian

Line 30 ⟶ 32:

==Applications and examples==

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

*The complement of an [[edgeless graph]] is a [[complete graph]] and vice versa.

*Any [[induced subgraph]] of the complement graph of a graph {{mvar|G}} is the complement of the corresponding induced subgraph in {{mvar|G}}.

Line 47 ⟶ 49:

| contribution-url = http://www.math.princeton.edu/~mchudnov/claws_survey.pdf

| volume = 327

| year = 2005}}..</ref> although the reverse is not true.

==Self-complementary graphs and graph classes==

Line 53 ⟶ 55:

{{main|Self-complementary graph}}

A [[self-complementary graph]] is a graph that is [[graph isomorphism|isomorphic]] to its own complement.<ref name="bm"/> Examples include the four-vertex [[path graph]] and five-vertex [[cycle graph]]. There is no known characterization of self-complementary graphs.

Several classes of graphs are self-complementary, in the sense that the complement of any graph in one of these classes is another graph in the same class.

Line 64 ⟶ 66:

| issue = 3

| pages = 253–267

| doi = 10.1016/0012-365X(72)90006-4| doi-access = free
}}.</ref>

*[[Cograph]]s are defined as the graphs that can be built up from single vertices by [[disjoint union]] and complementation operations. They form a self-complementary family of graphs: the complement of any cograph is another different cograph. For cographs of more than one vertex, exactly one graph in each complementary pair is connected, and one equivalent definition of cographs is that each of their connected [[induced subgraph]]s has a disconnected complement. Another, self-complementary definition is that they are the graphs with no induced subgraph in the form of a four-vertex path.<ref>{{Citation | last1=Corneil | first1=D. G. | author1-link = Derek Corneil | last2=Lerchs | first2=H. | last3=Stewart Burlingham | first3=L. | title=Complement reducible graphs | doi=10.1016/0166-218X(81)90013-5 | mr=0619603 | year=1981 | journal=[[Discrete Applied Mathematics]] | volume=3 | pages=163–174 | issue=3| doi-access=free }}.</ref>

*Another self-complementary class of graphs is the class of [[split graph]]s, the graphs in which the vertices can be partitioned into a clique and an independent set. The same partition gives an independent set and a clique in the complement graph.<ref>{{citation

| last = Golumbic | first = Martin Charles | authorlink = Martin Charles Golumbic