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

Research output: Contribution to journalArticlepeer-review

Abstract

Let F(x) = n=1s1,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.

Original languageEnglish
Pages (from-to)87-94
Number of pages8
JournalAlgebra Colloquium
Volume27
Issue number1
DOIs
Publication statusPublished - 1 Mar 2020

Keywords

  • Chebyshev polynomial
  • circulant graph
  • generating function
  • spanning tree
  • JACOBIAN GROUP
  • COMPLEXITY
  • FORMULAS

Fingerprint Dive into the research topics of 'On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs'. Together they form a unique fingerprint.

Cite this