On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs

Let F(x) = Sigma(infinity)(n=1) tau(s1,) (s2, ..)(.,)( sk) (n)x(n) be the generating function for the number tau(s1,) (s2, ..)(.,)( sk) (n) of spanning trees in the circulant graph C-n (s(1), s(2), ..., s(k)). We show that F(x) is a rational function with integer coefficients satisfying the property F(x) = F(1/x). A similar result is also true for the circulant graphs C-2n (s(1), s(2), ..., s(k), n) of odd valency. We illustrate the obtained results by a series of examples.