DIMACS TR: 2004-17

Further Analysis of the Number of Spanning Trees in Circulant Graphs

Authors: Talip Atajan, Xuerong Yong and Hiroshi Inaba

Let $1\leq s_1<s_2<\cdots<s_k\leq [n/2]$ be given integers. An undirected circulant graph, $C_n^{s_1,s_2,\cdots,s_k}, $ has $n$ vertices $0,\ 1,\ 2,\ \cdots$, $n-1$, and for each $s_i\ (1\leq i\leq k)$ and $j$ ($0\leq j \leq n-1$) there is an edge between $j$ and $j + s_i\ \bmod n$. Let $T(C_n^{s_1,s_2,\cdots,s_k})$ stand for the number of spanning trees of $C_n^{s_1,s_2,\cdots,s_k}$. For this special class of graphs, a general and most recent result is obtained in [Y. P. Zhang, X. Yong , M. J. Golin, The number of spanning trees in circulant graphs, Discrete Mathematics 223 (2000) 337-350.] where it is shown that $T(C_n^{s_1,s_2,\cdots,s_k})=na_n^2$ where $a_n$ satisfies a linear recurrence relation of order $2^{s_k-1}$.

In this paper we obtain further properties of the numbers $a_n$ by considering their combinatorial structures. Using these properties we answer the open problem posed in the Conclusion of [Y. P. Zhang, X. Yong, M. J. Golin.]. As examples, we describe our technique and asymptotic properties of the numbers.

Key Words: Circulant graphs; number of spanning trees

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-17.ps.gz

DIMACS Home Page