On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs Full article
| Journal |
Algebra Colloquium
ISSN: 1005-3867 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2020, Volume: 27, Number: 1, Pages: 87-94 Pages count : 8 DOI: 10.1142/S1005386720000085 | ||||
| Tags | Chebyshev polynomial; circulant graph; generating function; spanning tree | ||||
| Authors |
|
||||
| Affiliations |
|
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.
Cite:
Mednykh A.D.
, Mednykh I.A.
On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs
Algebra Colloquium. 2020. V.27. N1. P.87-94. DOI: 10.1142/S1005386720000085 WOS Scopus OpenAlex
On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs
Algebra Colloquium. 2020. V.27. N1. P.87-94. DOI: 10.1142/S1005386720000085 WOS Scopus OpenAlex
Identifiers:
| Web of science: | WOS:000518157600008 |
| Scopus: | 2-s2.0-85080125218 |
| OpenAlex: | W3008816466 |