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 $ntoinfty$ through the Mahler measure of the associated voltage polynomial. We also prove that $F(x)=sumlimits_{n=1}^inftytau(n)x^n$ is a rational function with integer coefficients.
Download