Cograph

From Wikipedia, the free encyclopedia

The Turán graph T(13,4), an example of a cograph.

In graph theory, the class of cographs (or complement-reducible graphs , or P4-free graphs) has been discovered independently by several authors since the 1970s; early references include Jung (1978), Lerchs (1971), Seinsche (1974), and Sumner (1974). It is the smallest class of graphs including the single vertex graph $K 1$ and closed under complementation and disjoint union. Thus any cograph may be constructed using the following rules:

any single vertex graph is a cograph;
if $G$ is a cograph, so is its complement $\overline{G}$ ;
if $G$ and $H$ are cographs, so is their disjoint union $G\cup H$ .

Several characterizations of cographs can be given. Among them:

A cograph is a graph which does not contain the path of length 3 as an induced path. That is, a graph is a cograph if and only if for any four vertices $v 1, v 2, v 3, v 4$ , if ${v 1, v 2},{v 2, v 3}$ and ${v 3, v 4}$ are edges of the graph then at least one of ${v 1, v 3},{v 1, v 4}$ or ${v 2, v 4}$ is also an edge.
A cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex.
A cograph is a graph in which every nontrivial induced subgraph has at least two vertices with the same neighbourhoods.
A cograph is a graph in which every connected induced subgraph has a disconnected complement.
A cograph is a graph all of whose connected induced subgraphs have diameter at most 2.
A cograph is a graph in which every connected component is a distance-hereditary graph with diameter at most 2.

All complete graphs, complete bipartite graphs, and Turán graphs are cographs. Every cograph is distance-hereditary, a comparability graph, and perfect.

1 Cotrees
2 Computational Properties
3 References
4 External links

[edit] Cotrees

A cograph and the corresponding cotree.

A cotree is a tree in which the internal nodes are labeled with the numbers 0 and 1. Every cotree T defines a cograph G having the leaves of T as vertices, and in which the subtree rooted at each node of T corresponds to the induced subgraph in G defined by the set of leaves descending from that node:

A subtree consisting of a single leaf node corresponds to an induced subgraph with a single vertex.
A subtree rooted at a node labeled 0 corresponds to the union of the subgraphs defined by the children of that node.
A subtree rooted at a node labeled 1 corresponds to the join of the subgraphs defined by the children of that node; that is, we form the union and add an edge between every two vertices corresponding to leaves in different subtrees. Alternatively, the join of a set of graphs can be viewed as formed by complementing each graph, forming the union of the complements, and then complementing the resulting union.

An equivalent way of describing the cograph formed from a cotree is that two vertices are connected by an edge if and only if the lowest common ancestor of the corresponding leaves is labeled by 1. Conversely, every cograph can be represented in this way by a cotree. If we require the labels on any root-leaf path of this tree to alternate between 0 and 1, this representation is unique (Corneil et al 1981).

[edit] Computational Properties

Cographs may be recognized in linear time, and a cotree representation constructed, using modular decomposition (Corneil et al. 1985) or more simply via partition refinement (Habib and Paul 2005). Once a cotree representation has been constructed, many familiar graph problems may be solved via simple bottom-up calculations on the cotrees.

For instance, to find the maximum clique in a cograph, compute in bottom-up order the maximum clique in each subgraph represented by a subtree of the cotree. For a node labeled 0, the maximum clique is the maximum among the cliques computed for that node's children. For a node labeled 1, the maximum clique is the union of the cliques computed for that node's children, and has size equal to the sum of the children's clique sizes. Thus, by alternately maximizing and summing values stored at each node of the cotree, we may compute the maximum clique size, and by alternately maximizing and taking unions, we may construct the maximum clique itself. Similar bottom-up tree computations allow the maximum independent set, vertex coloring number, maximum clique cover, and Hamiltonicity (that is the existence of a Hamiltonian cycle) to be computed in linear time from a cotree representation of a cograph. One can also use cotrees to determine in linear time whether two cographs are isomorphic.

[edit] References

Corneil, D. G.; Lerchs, H.; Burlingham, L. Stewart (1981). "Complement reducible graphs". Discrete Applied Mathematics 3: 163-174. DOI:10.1016/0166-218X(81)90013-5. MR 0619603.

Corneil, D. G.; Perl, Y.; Stewart, L. K. (1985). "A linear recognition algorithm for cographs". SIAM J. Comput. 14 (4): 926–934. DOI:10.1137/0214065. MR 0807891.

Habib, Michel; Paul, Christophe (2005). "A simple linear time algorithm for cograph recognition". Discrete Applied Mathematics 145: 183–197. DOI:10.1016/j.dam.2004.01.011. MR 2113140.

Jung, H. A. (1978). "On a class of posets and the corresponding comparability graphs". Journal of Combinatorial Theory, Series B 24: 125–133. MR 0491356.