Complement graph: Difference between revisions

Revision as of 21:36, 10 February 2016

Revision as of 21:48, 10 February 2016

Line 25:

==Applications and examples==

Several graph-theoretic concepts are related to each other via complement graphs:

*The vertices of the [[w:Kneser graph|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 [[:en:Johnson graph|Johnson graph]] J(''n'',''k''), where the edges are between intersecting sets.

*The complement of an [[edgeless graph]] is a [[complete graph]] and vice versa.

*AnAny [[independentinduced set (graph theory)|independent setsubgraph]] inof athe complement graph isof a [[clique (graph theory){{mvar|clique]]G}} inis the complement graphof andthe corresponding viceinduced versasubgraph in {{mvar|G}}.

*An [[independent set (graph theory)|independent set]] in a graph is a [[clique (graph theory)|clique]] in the complement graph and vice versa. This is a special case of the previous two properties, as an independent set is an edgeless induced subgraph and a clique is a complete induced subgraph.

*The complement of every [[triangle-free graph]] is a [[claw-free graph]],<ref>{{Citation

| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky

Line 42:

| 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,. andThey form a self-complementary family of graphs: the complement of any cograph is another (possibly 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 [[w:Kneser graph|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 [[:en:Johnson graph|Johnson graph]] J(''n'',''k''), where the edges are between intersecting sets.

==References==