Counting the number of spanning trees in some special graphs.

摘要

The number of spanning trees in a (di-)graph (network) is an important, well-studied quantity. Most research about the number of spanning trees is devoted to determining exact formulae for the number of spanning trees in many kinds of special graphs.; In this thesis, we start by stating the general methods for counting the number of spanning trees in (di-)graphs. We then discuss our new results. We show that the number of spanning trees in the circulant graph always satisfies a recurrence relation and describe how to derive this relation. The asymptotic behavior of these quantities are also derived. Boesch and Prodinger have shown how to use Chebyshev polynomials to derive closed formulae for the number of spanning trees of graphs in certain classes. This work has been extended to develop new techniques for the evaluation of the number of spanning trees in circulant graphs and graphs related to circulant graphs. We end by describing a method of counting the number of spanning trees in one class of double fixed-step loop networks.