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

• 来源期刊: 代数集刊（英文版）
• 关键词: spanning tree circulant graph Chebyshev polynomial generating function
• 年，卷（期）: 2020,（1）
• 页码范围: 87-94
• 页数: 8页
• 语种: 英文
• DOI: 10.1142/S1005386720000085

摘要

Let F(x) =∑∞n=1τs1,s2,...,sk (n)xn be the generating function for the number τs1,s2,...,sk (n) of spanning trees in the circulant graph Cn (s1,s2,...,sk).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 C2n(s1,s2,...,sk,n) of odd valency.We illustrate the obtained results by a series of examples.