Циклические накрытия графов. Перечисление отмеченных остовных лесов и деревьев, индекс Кирхгофа и якобианы Full article
| Journal |
Успехи математических наук
ISSN: 0042-1316 , E-ISSN: 2305-2872 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2023, Volume: 78, Number: 3(471), Pages: 115-164 Pages count : 50 DOI: 10.4213/rm10098 | ||||
| Tags | граф, якобиан, абелева группа, остовные деревья, отмеченные остовные леса, индекс Кирхгофа, числа Фибоначчи, полиномы Чебышёва | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 |
Министерство науки и высшего образования РФ Mathematical Center in Akademgorodok |
075-15-2019-1613, 075-15-2022-281 |
Abstract:
Цель настоящего обзора– изучение инвариантов циклических накрытий графов. При этом накрываемый граф предполагается фиксированным, а циклическая группа накрытия имеет сколь угодно большой порядок. Классическим примером такого накрытия является циркулянтный граф. Он накрывает одновершинный граф с заданным числом петель. Более сложными представителями семейства циклических накрытий являются I-, Y-, H-графы, обобщенные графы Петерсена, сэндвич-графы, дискретные торы и многие другие. В обзоре приведены аналитические формулы, позволяющие вычислять число отмеченных остовных лесов и деревьев в циклических накрытиях, найдена их асимптотика и изучены арифметические свойства этих чисел. Кроме того, для циркулянтных графов указаны точные формулы для вычисления индекса Кирхгофа и приведены структурные теоремы о строении якобианов таких графов.
Cite:
Медных А.Д.
, Медных И.А.
Циклические накрытия графов. Перечисление отмеченных остовных лесов и деревьев, индекс Кирхгофа и якобианы
Успехи математических наук. 2023. Т.78. №3(471). С.115-164. DOI: 10.4213/rm10098 РИНЦ MathNet OpenAlex
Циклические накрытия графов. Перечисление отмеченных остовных лесов и деревьев, индекс Кирхгофа и якобианы
Успехи математических наук. 2023. Т.78. №3(471). С.115-164. DOI: 10.4213/rm10098 РИНЦ MathNet OpenAlex
Translated:
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
Dates:
| Submitted: | May 6, 2022 |
| Published online: | May 31, 2023 |
| Published print: | Jul 18, 2023 |
Identifiers:
| Elibrary: | 54945872 |
| MathNet: | rm10098 |
| OpenAlex: | W4378880358 |