Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Complement graph
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{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 | authorlink1=John Adrian Bondy | last2=Murty | first2=U. S. R. | authorlink2=U. S. R. Murty | title=Graph Theory with Applications | year=1976 | publisher=North-Holland | isbn=0-444-19451-7 | url=https://archive.org/details/graphtheorywitha0000bond/page/6 | page=[https://archive.org/details/graphtheorywitha0000bond/page/6 6] }}.</ref> The complement is not the [[complement (set theory)|set complement]] of the graph; only the edges are complemented. ==Definition== Let {{math|1=''G'' = (''V'', ''E'')}} be a [[simple graph]] and let {{mvar|K}} consist of all 2-element subsets of {{mvar|V}}. Then {{math|1=''H'' = (''V'', ''K'' \ ''E'')}} is the complement of {{mvar|G}},<ref>{{Citation | last=Diestel | first=Reinhard | title=Graph Theory | publisher=[[Springer Science+Business Media|Springer]] | year=2005 | edition=3rd | isbn=3-540-26182-6 }}. [http://diestel-graph-theory.com/index.html Electronic edition], page 4.</ref> where {{math|''K'' \ ''E''}} is the [[relative complement]] of {{mvar|E}} in {{mvar|K}}. 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. In terms of the [[adjacency matrix]] ''A'' of the graph, if ''Q'' is the adjacency matrix of the [[complete graph]] of the same number of vertices (i.e. all entries are unity except the diagonal entries which are zero), then the adjacency matrix of the complement of ''A'' is ''Q-A''. 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. ==Applications and examples== Several graph-theoretic concepts are related to each other via complementation: *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}}. *An [[independent set (graph theory)|independent set]] in a graph is a [[clique (graph theory)|clique]] in the complement graph and vice versa. This is a special case of the previous two properties, as an independent set is an edgeless induced subgraph and a clique is a complete induced subgraph. *The [[Graph automorphism|automorphism]] group of a graph is the automorphism group of its complement. *The complement of every [[triangle-free graph]] is a [[claw-free graph]],<ref>{{Citation | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | contribution = The structure of claw-free graphs | mr = 2187738 | location = Cambridge | pages = 153–171 | publisher = Cambridge Univ. Press | series = London Math. Soc. Lecture Note Ser. | title = Surveys in combinatorics 2005 | 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== [[File:Self-complementary NZ graph.svg|thumb|upright=0.65|The four-vertex path is self-complementary.]] {{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. *[[Perfect graph]]s are the graphs in which, for every induced subgraph, the [[chromatic number]] equals the size of the maximum clique. The fact that the complement of a perfect graph is also perfect is the [[perfect graph theorem]] of [[László Lovász]].<ref>{{citation | last = Lovász | first = László | authorlink = László Lovász | year = 1972a | title = Normal hypergraphs and the perfect graph conjecture | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | volume = 2 | 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 | title = Algorithmic Graph Theory and Perfect Graphs | at = Theorem 6.1, p. 150 | publisher = Academic Press | year = 1980 | isbn = 0-12-289260-7 | mr = 0562306}}.</ref> *The [[threshold graph]]s are the graphs formed by repeatedly adding either an independent vertex (one with no neighbors) or a [[universal vertex]] (adjacent to all previously-added vertices). These two operations are complementary and they generate a self-complementary class of graphs.<ref>{{citation | last1 = Golumbic | first1 = Martin Charles | last2 = Jamison | first2 = Robert E. | doi = 10.1002/jgt.20163 | issue = 4 | journal = Journal of Graph Theory | mr = 2242832 | pages = 317–340 | title = Rank-tolerance graph classes | volume = 52 | year = 2006}}.</ref> ==Algorithmic aspects== In the [[analysis of algorithms]] on graphs, the distinction between a graph and its complement is an important one, because a [[sparse graph]] (one with a small number of edges compared to the number of pairs of vertices) will in general not have a sparse complement, and so an algorithm that takes time proportional to the number of edges on a given graph may take a much larger amount of time if the same algorithm is run on an explicit representation of the complement graph. Therefore, researchers have studied algorithms that perform standard graph computations on the complement of an input graph, using an [[implicit graph]] representation that does not require the explicit construction of the complement graph. In particular, it is possible to simulate either [[depth-first search]] or [[breadth-first search]] on the complement graph, in an amount of time that is linear in the size of the given graph, even when the complement graph may have a much larger size.<ref name="iy98"/> It is also possible to use these simulations to compute other properties concerning the connectivity of the complement graph.<ref name="iy98">{{citation | last1 = Ito | first1 = Hiro | last2 = Yokoyama | first2 = Mitsuo | doi = 10.1016/S0020-0190(98)00071-4 | issue = 4 | journal = [[Information Processing Letters]] | mr = 1629714 | pages = 209–213 | title = Linear time algorithms for graph search and connectivity determination on complement graphs | volume = 66 | year = 1998}}.</ref><ref>{{citation | last1 = Kao | first1 = Ming-Yang | last2 = Occhiogrosso | first2 = Neill | last3 = Teng | first3 = Shang-Hua | author3-link = Shang-Hua Teng | doi = 10.1023/A:1009720402326 | issue = 4 | journal = Journal of Combinatorial Optimization | mr = 1669307 | pages = 351–359 | title = Simple and efficient graph compression schemes for dense and complement graphs | volume = 2 | year = 1999}}.</ref> ==References== {{reflist|30em}} [[Category:Graph operations]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Citation
(
edit
)
Template:Main
(
edit
)
Template:Math
(
edit
)
Template:Mvar
(
edit
)
Template:Reflist
(
edit
)
Template:Short description
(
edit
)