TY - JOUR

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

AU - Mednykh, A. D.

AU - Mednykh, I. A.

N1 - Publisher Copyright: © 2020 Academy of Mathematics and Systems Science, Chinese Academy of Sciences. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/3/1

Y1 - 2020/3/1

N2 - 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.

AB - 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.

KW - Chebyshev polynomial

KW - circulant graph

KW - generating function

KW - spanning tree

KW - JACOBIAN GROUP

KW - COMPLEXITY

KW - FORMULAS

UR - http://www.scopus.com/inward/record.url?scp=85080125218&partnerID=8YFLogxK

U2 - 10.1142/S1005386720000085

DO - 10.1142/S1005386720000085

M3 - Article

AN - SCOPUS:85080125218

VL - 27

SP - 87

EP - 94

JO - Algebra Colloquium

JF - Algebra Colloquium

SN - 1005-3867

IS - 1

ER -