Complement graph: Difference between revisions

Revision as of 20:50, 16 May 2021

Latest revision as of 22:13, 23 June 2023

(3 intermediate revisions by 3 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 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 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