DIMACS TR: 2004-18
The number of spanning trees in circulant graphs with non-fixed
jumps
Authors: Yuanping Zhang, Zhiyong Zhang and Xuerong Yong
ABSTRACT
Let $1\leq s_1<s_2<\cdots<s_k$, and $q<p$ be given integers.
An {\em undirected circulant graph}, $C_n^{s_1,s_2,\cdots,s_k},
~$ has $n$ vertices labelled $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})$ be the number of spanning
trees of $C_n^{s_1,s_2,\cdots,s_k}$. We proved in \cite{kn:ZHANG00}
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 show that
$T(C_{pn}^{s_1,s_2,\cdots,s_k,qn})$ can be splitted into the products of
$T(C_n^{s_1,s_2,\cdots,s_k})$ and $\frac{1}{p}c_{n,p,q}^2$, where $c_{n,p,q}$
satisfies a linear recurrence relation for some $p,\ q$.
As examples of its use,
we describe the method and, for certain $p,q$, we provide the recurrence
relations
and the asymptotics of $T(C_{pn}^{s_1,s_2,\cdots,s_k,qn})$.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-18.ps.gz
DIMACS Home Page