The numbers of spanning trees in undirected circulant graphs. (Chinese. English summary) Zbl 0979.05063

Summary: Let \(1\leq a_1< a_2<\cdots< a_k< n/2\) and \(\text{gcd}(a_1, a_2,\dots, a_k)= 1\). Let \(C_n[a_1, a_2,\dots, a_k]\) be an undirected circulant graph and \(t(C_n[a_1, a_2,\dots, a_k])\) the number of its spanning trees. Suppose that \[ f(x)= \sum^k_{i=1} x^{a_k- a_i}(1+ x+ x^2+\cdots+ x^{a_i-1})^2. \] The roots with modules greater than \(1\) are \(\lambda_i\), \(i= 1,2,\dots, a_k-1\). We prove that \[ \begin{split} t(C_n[a_1, a_2,\dots, a_k])= {n\over f(1)} \prod^{a_k- 1}_{i=1} (-\lambda_i)^n(1- \lambda^{-n}_i)^2\sim {n\over f(1)} r^n,\quad n\to\infty,\\ \text{where}\quad r= \prod^{a_k-1}_{i= 1} (-\lambda_i)> 1.\end{split} \] Some examples are also given.


05C30 Enumeration in graph theory
05C05 Trees