Counting Spanning Trees in Cographs: .An Algorithmic Approach

Abstract

In this paper, we present a new simple linear-time algorithm for determining the number of spanning trees in the class of complement reducible graphs, also known as cographs. For a cograph $G$ on $n$ vertices and $m$ edges, our algorithm computes the number of spanning trees of $G$ in $O(n+m)$ time and space, where the complexity of arithmetic operations is measured under the uniform cost criterion. The algorithm takes advantage of the cotree of the input cograph $G$ and works by contracting it in a bottom-up fashion until it becomes a single node. Then, the number of spanning trees of $G$ is computed as the product of a collection of values which are associated with the vertices of $G$ and are updated during the contraction process. The correctness of our algorithm is established through the Kirchhoff matrix tree theorem, and also relies on structural and algorithmic properties of the class of cographs. We also extend our results to a proper superclass of cographs, namely the $P_4$-reducible graphs, and show that the problem of finding the number of spanning trees of a $P_4$-reducible graph has a linear-time solution.