DIMACS TR: 2004-17
Further Analysis of the Number of Spanning Trees in Circulant
Graphs
Authors: Talip Atajan, Xuerong Yong and Hiroshi Inaba
ABSTRACT
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