zbMATH — the first resource for mathematics

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.

MSC:
 05C30 Enumeration in graph theory 05C05 Trees
Keywords:
circulant graph; spanning trees