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

Standard

On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs. / Mednykh, A. D.; Mednykh, I. A.

In: Algebra Colloquium, Vol. 27, No. 1, 01.03.2020, p. 87-94.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{e46bd9d4359044e78c5debc2cd13fc6c,

title = "On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs",

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.",

keywords = "Chebyshev polynomial, circulant graph, generating function, spanning tree, JACOBIAN GROUP, COMPLEXITY, FORMULAS",

author = "Mednykh, {A. D.} and Mednykh, {I. A.}",

year = "2020",

month = mar,

day = "1",

doi = "10.1142/S1005386720000085",

language = "English",

volume = "27",

pages = "87--94",

journal = "Algebra Colloquium",

issn = "1005-3867",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "1",

}

RIS

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.

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 -

ID: 23666804