On rationality of generating function for the number of spanning trees in circulant graphs

2018/11/09 by Mednykh, A. D., Mednykh, I. A. · 2 citations
#05C30 #39A10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1811.03803

Abstract

Let F(x)=∑_n=1^∞τ(n)xⁿ be the generating function for the number τ(n) of spanning trees in the circulant graphs C_n(s₁,s₂,…,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 of odd valency C_2n(s₁,s₂,…,s_k,n). We illustrate the obtained results by a series of examples.

Cited by

• The number of rooted spanning forests of bicirculant graphs
• Chebyshev Recurrence Structures for Reduced Spectral Functions of Cyclic Circulant Graphs

Related

• The number of spanning trees in circulant graphs, its arithmetic\n properties and asymptotic
• The number of rooted forests in circulant graphs
• Automated Counting of Spanning Trees for Several Infinite Families of Graphs
• A formula for the number of the spanning trees of line graphs
• Complexity of the circulant foliation over a graph