Content deleted Content added
→Applications and examples: examples of self-complementary |
→Applications and examples: source claw-free |
||
Line 27:
*The complement of an [[edgeless graph]] is a [[complete graph]] and vice versa.
*An [[independent set (graph theory)|independent set]] in a graph is a [[clique (graph theory)|clique]] in the complement graph and vice versa.
*The complement of
| 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.
*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]].
*[[Cograph]]s are defined as the graphs that can be built up from [[disjoint union]] and complementation operations, and form a self-complementary family of graphs: the complement of any cograph is another (possibly different) cograph.
| |||