Content deleted Content added
→Applications and examples: source Kneser/Johnson complementarity |
|||
Line 43:
*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 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}}.</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 vertices of the [[Kneser graph]] KG(''n'',''k'') are the ''k''-subsets of an ''n''-set, and the edges are between [[Disjoint sets|disjoint]] sets. The complement is the [[Johnson graph]] J(''n'',''k''), where the edges are between intersecting sets.<ref>{{citation
| last1 = Bailey | first1 = Robert F.
| |||