DIMACS TR: 2004-18

The number of spanning trees in circulant graphs with non-fixed jumps

Authors: Yuanping Zhang, Zhiyong Zhang and Xuerong Yong

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