The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic

Alexander Mednykh, Ilya Mednykh

Published 2017-11-01Version 1

In this paper, we develop a new method to produce explicit formulas for the number $\tau(n)$ of spanning trees in the undirected circulant graphs $C_{n}(s_1,s_2,\ldots,s_k)$ and $C_{2n}(s_1,s_2,\ldots,s_k,n).$ Also, we prove that in both cases the number of spanning trees can be represented in the form $\tau(n)=p \,n \,a(n)^2,$ where $a(n)$ is an integer sequence and $p$ is a prescribed natural number depending only of parity of $n.$ Finally, we find an asymptotic formula for $\tau(n)$ through the Mahler measure of the associated Laurent polynomial $L(z)=2k-\sum\limits_{i=1}^k(z^{s_i}+z^{-s_i}).$