Content deleted Content added
Removed incorrect example: the complement of Kneser graph is not a Johnson graph (although it is a graph in a Johnson scheme). |
Add fact that automorphism group of graph complement is automorphism group of original graph. |
||
Line 27:
*Any [[induced subgraph]] of the complement graph of a graph {{mvar|G}} is the complement of the corresponding induced subgraph 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 [[Graph automorphism|automorphism]] group of a graph is the automorphism group of its complement.
*The complement of every [[triangle-free graph]] is a [[claw-free graph]],<ref>{{Citation
| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
| |||