TOPICS

# Cograph

A cograph (or "complement-reducible graph") is simple graph defined by the criteria

1. is a cograph,

2. If is a cograph, then so is its graph complement, and

3. If and are cographs, then so is their graph union

Note that cographs have been discovered independently many times since the 1970s, so no particular definition or terminology should be considered standard. Brandstadt et al. (1999) contains references for many of the independent discoveries/definitions/characterizations of cographs.

A graph is a cograph if any of the following equivalent conditions holds:

1. can be constructed from isolated vertices by disjoint union and graph join operations.

2. is the disjoint union of distance-hereditary graphs with diameter at most 2.

3. In every induced subgraph of , the intersection of any maximal clique and any maximum independent vertex set contains precisely one vertex.

4. Every nontrivial subgraph of has at least one pair of twins (i.e., two vertices with the same neighborhoods).

5. The graph complement of every nontrivial connected subgraph of is disconnected.

6. Every connected subgraph of has diameter at most 2.

7. does not contain the path graph as an induced subgraph.

The numbers of cographs on , 2, ... nodes are 1, 2, 4, 10, 24, 66, 180, 522, 1532, ... (OEIS A000084). Brandstadt et al. (1999, definition 1.5) note that a graph is a cograph if its modular decomposition tree contains only parallel and series nodes. More specifically and explicitly, the counts of cographs on nodes are the same as the counts of series-parallel networks with unlabeled edges, as noted by Weisstein (2003ab) and proved by Sloane. The first cographs on to 5 nodes are illustrated above. For , the number of cographs is always even.

Graph Complement, Path Graph, Series-Parallel Graph, Series-Parallel Network

## References

Brandstadt, A.; Le, V. B.; Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, 1999.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. New York: Springer-Verlag, p. 435, 1989.Corneil, D. H.; Lerchs, H.; and Stewart Burlingham, L. "Complement Reducible Graphs." Discr. Appl. Math. 3, 163-174, 1981.Sloane, N. J. A. Sequence A000084/M1207 in "The On-Line Encyclopedia of Integer Sequences."Weisstein, E. W. "Re: Cographs." Oct. 9, 2003a. http://listserv.nodak.edu/scripts/wa.exe?A2=ind0310&L=graphnet&P=R743.Weisstein, E. W. "Cographs <=> Series-Parallel Networks." Oct. 23, 2003b. http://listserv.nodak.edu/scripts/wa.exe?A2=ind0310&L=graphnet&P=R1929.

Cograph

## Cite this as:

Weisstein, Eric W. "Cograph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Cograph.html