Content deleted Content added
→Applications and examples: split off self-complementary into separate section; add perfect and threshold |
|||
Line 41:
| 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 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.
Line 67 ⟶ 57:
| volume = 34
| year = 2013}}.</ref>
==Self-complementary graphs and graph classes==
▲
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}}.</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}}.</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>
==References==
| |||