Content deleted Content added
→Self-complementary graphs and graph classes: No classification. |
m Open access bot: doi added to citation with #oabot. |
||
Line 64:
| 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
| |||