A formula for the number of spanning trees in circulant graphs with non-fixed generators and discrete tori

Abstract

We consider the number of spanning trees in circulant graphs of $\beta n$ vertices with generators depending linearly on $n$. The matrix tree theorem gives a closed formula of $\beta n$ factors, while we derive a formula of $\beta -1$ factors. Using the same trick, we also derive a formula for the number of spanning trees in discrete tori. Moreover, the spanning tree entropy of circulant graphs with fixed and non-fixed generators is compared.

8 pages, 2 figures

References in corpus (1)

• Asymptotics for the number of spanning trees in circulant graphs and degenerating d-dimensional discrete tori