On complexity of cyclic coverings of graphs

Abstract

By complexity of a finite graph we mean the number of spanning trees in the graph. The aim of the present paper is to give a new approach for counting complexity $\tau (n)$ of cyclic $n$-fold coverings of a graph. We give an explicit analytic formula for $\tau (n)$ in terms of Chebyshev polynomials and find its asymptotic behavior as $n\to \infty$ through the Mahler measure of the associated voltage polynomial. We also prove that $F(x)=\sum _{n=1}^{\infty }\tau (n)x^n$ is a rational function with integer coefficients.

19 pages, 4 figures