Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians

Standard

Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians. / Mednykh, Alexander D.; Mednykh, Il’Ya A.

In: Russian Mathematical Surveys, Vol. 78, No. 3, 2023, p. 501-548.

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

BibTeX

@article{dcb7a87438694c7fa839a09e1e760645,

title = "Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians",

abstract = "The purpose of this survey is to describe invariants of cyclic coverings of graphs. The covered graph is assumed to be fixed, and the cyclic covering group has an arbitrarily large order. A classical example of such a covering is a circulant graph. It covers a one-vertex graph with a prescribed number of loops. More sophisticated objects representing the family of cyclic coverings include I-, Y-, and H-graphs, generalized Petersen graphs, sandwich-graphs, discrete tori, and many others. We present ana-lytic formulae for counting rooted spanning forests and trees in cyclic cov-erings, establish their asymptotics, and study the arithmetic properties of these quantities. Moreover, in the case of circulant graphs we give exact formulae for computing the Kirchhoff index and present structural theorems for the Jacobians of such graphs. Bibliography: 95 titles.",

keywords = "Abelian group, Chebyshev polynomials, Fibonacci numbers, Jacobian, Kirchhoff index, graph, rooted spanning forests, spanning trees",

author = "Mednykh, {Alexander D.} and Mednykh, {Il{\textquoteright}Ya A.}",

note = "The work was supported by the Mathematical Center in Akademgorodok under agreement no. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation. AMS 2020 Mathematics Subject Classification. Primary 05C05, 05C25, 05C50; Secondary 57M15.",

year = "2023",

doi = "10.4213/rm10098e",

language = "English",

volume = "78",

pages = "501--548",

journal = "Russian Mathematical Surveys",

issn = "0036-0279",

publisher = "IOP Publishing Ltd.",

number = "3",

}

RIS

TY - JOUR

T1 - Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians

AU - Mednykh, Alexander D.

AU - Mednykh, Il’Ya A.

N1 - The work was supported by the Mathematical Center in Akademgorodok under agreement no. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation. AMS 2020 Mathematics Subject Classification. Primary 05C05, 05C25, 05C50; Secondary 57M15.

PY - 2023

Y1 - 2023

N2 - The purpose of this survey is to describe invariants of cyclic coverings of graphs. The covered graph is assumed to be fixed, and the cyclic covering group has an arbitrarily large order. A classical example of such a covering is a circulant graph. It covers a one-vertex graph with a prescribed number of loops. More sophisticated objects representing the family of cyclic coverings include I-, Y-, and H-graphs, generalized Petersen graphs, sandwich-graphs, discrete tori, and many others. We present ana-lytic formulae for counting rooted spanning forests and trees in cyclic cov-erings, establish their asymptotics, and study the arithmetic properties of these quantities. Moreover, in the case of circulant graphs we give exact formulae for computing the Kirchhoff index and present structural theorems for the Jacobians of such graphs. Bibliography: 95 titles.

AB - The purpose of this survey is to describe invariants of cyclic coverings of graphs. The covered graph is assumed to be fixed, and the cyclic covering group has an arbitrarily large order. A classical example of such a covering is a circulant graph. It covers a one-vertex graph with a prescribed number of loops. More sophisticated objects representing the family of cyclic coverings include I-, Y-, and H-graphs, generalized Petersen graphs, sandwich-graphs, discrete tori, and many others. We present ana-lytic formulae for counting rooted spanning forests and trees in cyclic cov-erings, establish their asymptotics, and study the arithmetic properties of these quantities. Moreover, in the case of circulant graphs we give exact formulae for computing the Kirchhoff index and present structural theorems for the Jacobians of such graphs. Bibliography: 95 titles.

KW - Abelian group

KW - Chebyshev polynomials

KW - Fibonacci numbers

KW - Jacobian

KW - Kirchhoff index

KW - graph

KW - rooted spanning forests

KW - spanning trees

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85179932172&origin=inward&txGid=21c0cf7486b427112981933a80ed8a41

UR - https://www.mendeley.com/catalogue/9f5b0347-65b9-357f-8541-b3ed1a9cb771/

U2 - 10.4213/rm10098e

DO - 10.4213/rm10098e

M3 - Article

VL - 78

SP - 501

EP - 548

JO - Russian Mathematical Surveys

JF - Russian Mathematical Surveys

SN - 0036-0279

IS - 3

ER -

ID: 59391303