Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians Full article
| Journal |
Russian Mathematical Surveys
ISSN: 0036-0279 , E-ISSN: 1468-4829 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2023, Volume: 78, Number: 3, Pages: 501-548 Pages count : 48 DOI: 10.4213/rm10098e | ||||
| Tags | graph, Jacobian, Abelian group, spanning trees, rooted spanning forests, Kirchhoff index, Fibonacci numbers, Chebyshev polynomials | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 |
Министерство науки и высшего образования РФ Mathematical Center in Akademgorodok |
075-15-2019-1613, 075-15-2022-281 |
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 analytic formulae for counting rooted spanning forests and trees in cyclic coverings, 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.
Cite:
Mednykh A.D.
, Mednykh I.A.
Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians
Russian Mathematical Surveys. 2023. V.78. N3. P.501-548. DOI: 10.4213/rm10098e WOS Scopus РИНЦ OpenAlex
Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians
Russian Mathematical Surveys. 2023. V.78. N3. P.501-548. DOI: 10.4213/rm10098e WOS Scopus РИНЦ OpenAlex
Original:
Медных А.Д.
, Медных И.А.
Циклические накрытия графов. Перечисление отмеченных остовных лесов и деревьев, индекс Кирхгофа и якобианы
Успехи математических наук. 2023. Т.78. №3(471). С.115-164. DOI: 10.4213/rm10098 РИНЦ MathNet OpenAlex
Циклические накрытия графов. Перечисление отмеченных остовных лесов и деревьев, индекс Кирхгофа и якобианы
Успехи математических наук. 2023. Т.78. №3(471). С.115-164. DOI: 10.4213/rm10098 РИНЦ MathNet OpenAlex
Dates:
| Submitted: | May 6, 2022 |
| Published print: | Dec 12, 2023 |
| Published online: | Dec 12, 2023 |
Identifiers:
| Web of science: | WOS:001146055900003 |
| Scopus: | 2-s2.0-85179932172 |
| Elibrary: | 65486922 |
| OpenAlex: | W4389318642 |