几族循环图的支撑树数

The Numbers of Spanning Trees of Some Families of the Circulant Graphs

设Cn（a1,a2,…，ak）是个循环图，t（G）是图G的支撑树数、本文利用第二类Chebyshev多项式给出了t（Cn（1，3）），t（Cn（2,3）），t（Cn（1，2，3）），t（Cn（3,5）），t（C2n（1,2,n））的公式.一个具体的例子表明，利用Chebyshev多项式的性质，即使n很大；

Let Cn (a1,a2,,ak ) be the circulant graph and t(G) be the number of spanning trees of a graph G. In this paper, the formulas for t(Cn (1,3)), t(Cn (2,3)), t(Cn (1,2,3)),t(C, (1,5)), t(Cn (3, 5)) and t(C2n. (1,2, n)) are obtained in terms of Chebyshev polynomials of the second kind. Using some properties of Chebyshev polynomials, one can easily obtain the values of these formulas even if n is large.Theorem 6. Let Fn, be the nth Fibonacci number and Un (x) Chebyshev polynomials of the second kind. Let If n≥ 3, then