Complement graph: Difference between revisions

Revision as of 21:48, 10 February 2016

Revision as of 23:23, 10 February 2016

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>

*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.

| last2 = Cáceres | first2 = José

| last3 = Garijo | first3 = Delia

| last4 = González | first4 = Antonio

| last5 = Márquez | first5 = Alberto

| last6 = Meagher | first6 = Karen

| last7 = Puertas | first7 = María Luz

| doi = 10.1016/j.ejc.2012.10.008

| issue = 4

| journal = [[European Journal of Combinatorics]]

| mr = 3010114

| pages = 736–751

| title = Resolving sets for Johnson and Kneser graphs

| volume = 34

| year = 2013}}.</ref>

==References==