Science Fair Project Encyclopedia
Cograph
In graph theory, a cograph, complement-reducible graph , or P4-free graph, is a graph that fulfills the following equivalent properties:
- Can be constructed from isolated vertices by complement, joint union and disjoint union.
- Can be decomposed by isolated vertex elimination and complement.
- It contains no induced path of length at least 4.
- The maximum distance between two vertices in the same connected component is at most 2.
- Has at least one pair of false or true twins (that have the same opened or closed neighbourhood).
Properties
- Polynomial recognition time:
- Since it has a characterization by a finite number of forbidden subgraphs.
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details