Content deleted Content added
→Self-complementary graphs and graph classes: {{main|Self-complementary graph}} |
move images around and add one |
||
Line 1:
[[File:Petersen graph complement.svg|thumb|upright=1.35|The [[Petersen graph]] (on the left) and its complement graph (on the right).]]
{{multiple image▼
|image1=Kneser graph KG(5,2).svg|caption1=The Petersen graph as Kneser graph KG(5,2) ...▼
|image2=Johnson graph J(5,2).svg|caption2=... and its complement the Johnson graph J(5,2)}}▼
In [[graph theory]], the '''complement''' or '''inverse''' of a graph ''G'' is a graph ''H'' on the same vertices such that two distinct 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.<ref name="bm">{{citation
| last1=Bondy | first1=John Adrian | authorlink1=John Adrian Bondy
Line 27 ⟶ 24:
==Applications and examples==
▲{{multiple image
▲|image1=Kneser graph KG(5,2).svg|caption1=The Petersen graph as Kneser graph KG(5,2) ...
▲|image2=Johnson graph J(5,2).svg|caption2=... and its complement the Johnson graph J(5,2)}}
Several graph-theoretic concepts are related to each other via complement graphs:
*The complement of an [[edgeless graph]] is a [[complete graph]] and vice versa.
Line 62:
==Self-complementary graphs and graph classes==
[[File:Self-complementary NZ graph.svg|thumb|upright=0.75|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]].
| |||