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

Abstract

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,\dots ,s_k)$ and $C_{2n}(s_1,s_2,\dots ,s_k,n).$ Also, we prove that in both cases the number of spanning trees can be represented in the form $\tau (n)=pna(n{)}^2,$ where $a(n)$ is an integer sequence and $p$ is a prescribed natural number depending on the 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 _{i=1}^k(z^{s_i}+z^{-s_i}).$

arXiv comment18 pages