Cyclic coverings of graphs. Enumeration of maked skeleton forests and trees, Krchhoff index, and Jacobians

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Цель настоящего обзора – изучение инвариантов циклических накрытий графов. При этом накрываемый граф предполагается фиксированным, а циклическая группа накрытия имеет сколь угодно большой порядок. Классическим примером такого накрытия является циркулянтный граф. Он накрывает одновершинный граф с заданным числом петель. Более сложными представителями семейства циклических накрытий являются $I$-, $Y$-, $H$-графы, обобщенные графы Петерсена, сэндвич-графы, дискретные торы и многие другие. В обзоре приведены аналитические формулы, позволяющие вычислять число отмеченных остовных лесов и деревьев в циклических накрытиях, найдена их асимптотика и изучены арифметические свойства этих чисел. Кроме того, для циркулянтных графов указаны точные формулы для вычисления индекса Кирхгофа и приведены структурные теоремы о строении якобианов таких графов. Библиография: 95 названий.

About the authors

Alexander Dmitrievich Mednykh

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University

Email: mednykh@math.nsc.ru
Doctor of physico-mathematical sciences, Professor

Il'ya Aleksandrovich Mednykh

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University

Email: ilyamednykh@mail.ru
Candidate of physico-mathematical sciences

References

  1. N. V. Abrosimov, G. A. Baigonakova, L. A. Grunwald, I. A. Mednykh, “Counting rooted spanning forests in cobordism of two circulant graphs”, Сиб. электрон. матем. изв., 17 (2020), 814–823
  2. N. V. Abrosimov, G. A. Baigonakova, I. A. Mednykh, “Counting spanning trees in cobordism of two circulant graphs”, Сиб. электрон. матем. изв., 15 (2018), 1145–1157
  3. A. Adam, “Research problem 2-10”, J. Combin. Theory, 2 (1967), 393
  4. R. Bacher, P. de la Harpe, T. Nagnibeda, “The lattice of integral flows and the lattice of integral cuts on a finite graph”, Bull. Soc. Math. France, 125:2 (1997), 167–198
  5. G. A. Baigonakova, A. D. Mednykh, “Elementary formulas for Kirchhoff index of Möbius ladder and prism graphs”, Сиб. электрон. матем. изв., 16 (2019), 1654–1661
  6. M. Baker, S. Norine, “Harmonic morphisms and hyperelliptic graphs”, Int. Math. Res. Not. IMRN, 2009:15 (2009), 2914–2955
  7. H. Bass, “Covering theory for graphs of groups”, J. Pure Appl. Algebra, 89:1-2 (1993), 3–47
  8. N. Biggs, “Three remarkable graphs”, Canad. J. Math., 25:2 (1973), 397–411
  9. N. L. Biggs, “Chip-firing and the critical group of a graph”, J. Algebraic Combin., 9:1 (1999), 25–45
  10. F. T. Boesch, Z. R. Bogdanowicz, “The number of spanning tress in a prism”, Internat. J. Comput. Math., 21:3-4 (1987), 229–243
  11. F. T. Boesch, H. Prodinger, “Spanning tree formulas and Chebyshev polynomials”, Graphs Combin., 2 (1986), 191–200
  12. D. W. Boyd, “Mahler's measure and invariants of hyperbolic manifolds”, Number theory for the millennium (Urbana, IL, 2000), v. I, A K Peters, Natick, MA, 2002, 127–143
  13. D. Calan, “A combinatorial derivation of the number of labeled forests”, J. Integer Seq., 6:4 (2003), 03.4.7, 9 pp.
  14. P. Chebotarev, “Spanning forests and the golden ratio”, Discrete Appl. Math., 156:5 (2008), 813–821
  15. P. Chebotarev, R. Agaev, “Forest matrices around the Laplacian matrix”, Linear Algebra Appl., 356:1-3 (2002), 253–274
  16. P. Chebotarev, E. Shamis, Matrix-forest theorems, 2006, 10 pp.
  17. Pingge Chen, Yaoping Hou, Chingwah Woo, “On the critical group of the Möbius ladder graph”, Australas. J. Combin., 36 (2006), 133–142
  18. Xiebin Chen, Qiuying Lin, Fuji Zhang, “The number of spanning trees in odd valent circulant graphs”, Discrete Math., 282:1-3 (2004), 69–79
  19. Z. Cinkir, “Effective resistances and Kirchhoff index of ladder graphs”, J. Math. Chem., 54:4 (2016), 955–966
  20. Z. Cinkir, Effective resistances and Kirchhoff index of prism graphs, 2017, 9 pp.
  21. M. Conder, R. Grande, “On embeddings of circulant graphs”, Electron. J. Combin., 22:2 (2015), P2.28, 27 pp.
  22. R. Cori, D. Rossin, “On the sandpile group of dual graphs”, European J. Combin., 21:4 (2000), 447–459
  23. P. J. Davis, Circulant matrices, 2nd ed., AMS Chelsea Publishing, New York, NY, 1994
  24. D. Dhar, P. Ruelle, S. Sen, D.-N. Verma, “Algebraic aspects of Abelian sandpile models”, J. Phys. A: Math. Gen., 28:4 (1995), 805–831
  25. С. А. Евдокимов, И. Н. Пономаренко, “Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время”, Алгебра и анализ, 15:6 (2003), 1–34
  26. G. Everest, T. Ward, Heights of polynomials and entropy in algebraic dynamics, Universitext, Springer-Verlag London, Ltd., London, 2013, 212 pp.
  27. C. Godsil, G. Royle, Algebraic graph theory, Grad. Texts in Math., 207, Springer-Verlag, New York, 2001, xx+439 pp.
  28. G. Goel, D. Perkinson, “Critical groups of iterated cones”, Linear Algebra Appl., 567 (2019), 138–142
  29. C. M. Gordon, “A short proof of a theorem of Plans on the homology of the branched cyclic coverings of a knot”, Bull. Amer. Math. Soc., 77 (1971), 85–87
  30. J. L. Gross, T. W. Tucker, Topological graph theory, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, Inc., New York, 1987, xvi+351 pp.
  31. L. A. Grunwald, Young Soo Kwon, I. A. Mednykh, “Counting rooted spanning forests for circulant foliation over a graph”, Tohoku Math. J. (2), 74:4 (2022), 535–548
  32. L. A. Grunwald, I. A. Mednykh, “On the Jacobian group of a cone over a circulant graph”, Математические заметки СВФУ, 28:2 (2021), 88–101
  33. L. A. Grunwald, I. A. Mednykh, “The number of rooted forests in circulant graphs”, Ars Math. Contemp., 22:4 (2022), 10, 12 pp.
  34. I. Gutman, B. Mohar, “The quasi-Wiener and the Kirchhoff indices coincide”, J. Chem. Inf. Comput. Sci., 36:5 (1996), 982–985
  35. A. J. Guttmann, M. D. Rogers, “Spanning tree generating functions and Mahler measures”, J. Phys. A, 45:49 (2012), 494001, 24 pp.
  36. A. J. W. Hilton, “Spanning trees and Fibonacci and Lucas numbers”, Fibonacci Quart., 12 (1974), 259–262
  37. J. D. Horton, I. Z. Bouwer, “Symmetric $Y$-graphs and $H$-graphs”, J. Combin. Theory Ser. B, 53:1 (1991), 114–129
  38. Yaoping Hou, Chingwah Woo, Pingge Chen, “On the sandpile group of the square cycle $C_n^2$”, Linear Algebra Appl., 418:2-3 (2006), 457–467
  39. Danrun Huang, “A cyclic six-term exact sequence for block matrices over a PID”, Linear Multilinear Algebra, 49:2 (2001), 91–114
  40. B. Jacobson, A. Niedermaier, V. Reiner, “Critical groups for complete multipartite graphs and Cartesian products of complete graphs”, J. Graph Theory, 44:3 (2003), 231–250
  41. J. L. V. W. Jensen, “Sur un nouvel et important theorème de la theorie des fonctions”, Acta Math., 22:1 (1899), 359–364
  42. Yinglie Jin, Chunlin Lin, “Enumeration for spanning forests of complete bipartite graphs”, Ars Combin., 70 (2004), 135–138
  43. M. Kagan, B. Mata, “A physics perspective on the resistance distance for graphs”, Math. Comput. Sci., 13:1-2 (2019), 105–115
  44. A. K. Kelmans, V. M. Chelnokov, “A certain polynomial of a graph and graphs with an extremal number of trees”, J. Combin. Theory Ser. B, 16:3 (1974), 197–214
  45. G. Kirchhoff, “Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird”, Ann. Phys. Chem., 72:12 (1847), 497–508
  46. D. J. Klein, M. Randic, “Resistance distance”, J. Math. Chem., 12:1-4 (1993), 81–95
  47. O. Knill, “Cauchy–Binet for pseudo-determinants”, Linear Algebra Appl., 459 (2014), 522–547
  48. M. Kotani, T. Sunada, “Jacobian tori associated with a finite graph and its Abelian covering graphs”, Adv. in Appl. Math., 24:2 (2000), 89–110
  49. Y. S. Kwon, A. D. Mednykh, I. A. Mednykh, “On Jacobian group and complexity of the generalized Petersen graph $GP(n,k)$ through Chebyshev polynomials”, Linear Algebra Appl., 529 (2017), 355–373
  50. Y. S. Kwon, A. D. Mednykh, I. A. Mednykh, On complexity of cyclic coverings of graphs, 2018, 19 pp.
  51. Y. S. Kwon, A. D. Mednykh, I. A. Mednykh, “Complexity of the circulant foliation over a graph”, J. Algebraic Combin., 53:1 (2021), 115–129
  52. D. H. Lehmer, “Factorization of certain cyclotomic functions”, Ann. of Math. (2), 34:3 (1933), 461–479
  53. C. J. Liu, Yutze Chow, “Enumeration of forests in a graph”, Proc. Amer. Math. Soc., 83:3 (1981), 659–662
  54. D. Lorenzini, “Smith normal form and Laplacians”, J. Combin. Theory Ser. B, 98:6 (2008), 1271–1300
  55. J. Louis, “A formula for the number of spanning trees in circulant graphs with nonfixed generators and discrete tori”, Bull. Aust. Math. Soc., 92:3 (2015), 365–373
  56. I. Lukovits, S. Nikolic, N. Trinajstic, “Resistance distance in regular graphs”, Int. J. Quantum Chem., 71:3 (1999), 217–225
  57. Ye Luzhen, “On the Kirchhoff index of some toroidal lattices”, Linear Multilinear Algebra, 59:6 (2011), 645–650
  58. K. Mahler, “On some inequalities for polynomials in several variables”, J. London Math. Soc., 37 (1962), 341–344
  59. У. Масси, Дж. Столлингс, Алгебраическая топология. Введение, Мир, М., 1977, 344 с.
  60. А. Д. Медных, И. А. Медных, “О строении группы якобиана циркулянтных графов”, Докл. РАН, 469:5 (2016), 539–543
  61. А. Д. Медных, И. А. Медных, “Об асимптотике и арифметических свойствах функции сложности циркулянтных графов”, Докл. РАН, 479:4 (2018), 363–367
  62. A. D. Mednykh, I. A. Mednykh, “The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic”, Discrete Math., 342:6 (2019), 1772–1781
  63. А. Д. Медных, И. А. Медных, “О строении критической группы циркулянтного графа с непостоянными скачками”, УМН, 75:1(451) (2020), 197–198
  64. А. Д. Медных, И. А. Медных, “Индекс Кирхгофа для циркулянтных графов и его асимптотика”, Докл. РАН. Матем., информ., проц. упр., 494 (2020), 43–47
  65. A. D. Mednykh, I. A. Mednykh, “On rationality of generating function for the number of spanning trees in circulant graphs”, Algebra Colloq., 27:1 (2020), 87–94
  66. А. Д. Медных, И. А. Медных, “О теореме Планса и периодичности якобианов циркулянтных графов”, Докл. РАН. Матем., информ., проц. упр., 498 (2021), 51–54
  67. A. Mednykh, I. Mednykh, “Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics”, Ars Math. Contemp., 23:1 (2023), 8, 16 pp.
  68. I. A. Mednykh, “On Jacobian group and complexity of the $I$-graph $I(n,k,l)$ through Chebyshev polynomials”, Arc Math. Contemp., 15:2 (2018), 467–485
  69. I. A. Mednykh, M. A. Zindinova, “On the structure of Picard group for Moebius ladder”, Сиб. электрон. матем. изв., 8 (2011), 54–61
  70. B. Mohar, “The Laplacian spectrum of graphs”, Graph theory, combinatorics, and applications (Kalamazoo, MI, 1988), v. 2, Wiley-Intersci. Publ., John Wiley & Sons, Inc., New York, 1991, 871–898
  71. M. Muzychuk, “A solution of the isomorphism problem for circulant graphs”, Proc. London Math. Soc. (3), 88:1 (2004), 1–41
  72. N. Neumärker, The arithmetic structure of discrete dynamical systems on the torus, PhD thesis, Univ. Bielefeld, Bielefeld, 2012, 92 pp., pp.
  73. J. L. Palacios, “Closed-form formulas for Kirchhoff index”, Int. J. Quantum Chem., 81:2 (2001), 135–140
  74. A. Plans, “Aportacion al estudio de los grupos de homologia de los recubrimientos ciclicos ramificados correspondientes a un nudo”, Rev. Acad. Ci. Madrid, 47 (1953), 161–193
  75. В. В. Прасолов, Многочлены, 3-е изд., МЦНМО, М., 2003, 336 с.
  76. M. Sakuma, “Homology of Abelian coverings of links and spatial graphs”, Canad. J. Math., 47:1 (1995), 201–224
  77. J. Sedlaček, “On the number of spanning trees of finite graphs”, Časopis Pěst. Mat., 94:2 (1969), 217–221
  78. J. Sedlacěk, “On the skeletons of a graph or digraph”, Combinatorial structures and their applications (Calgary, 1969), Gordon and Breach Sci. Publ., New York–London–Paris, 1970, 387–391
  79. R. Shrock, F. Y. Wu, “Spanning trees on graphs and lattices in $d$ dimensions”, J. Phys. A, 33:21 (2000), 3881–3902
  80. D. S. Silver, S. G. Williams, Spanning trees and Mahler measure, 2016, 12 pp.
  81. D. S. Silver, S. G. Williams, Graph complexity and Mahler measure, 2017, 16 pp.
  82. Ch. Smyth, “The Mahler measure of algebraic numbers: a survey”, Number theory and polynomials, London Math. Soc. Lecture Note Ser., 352, Cambridge Univ. Press, Cambridge, 2008, 322–349
  83. A. Steimle, W. Staton, “The isomorphism classes of the generalized Petersen graphs”, Discrete Math., 309:1 (2009), 231–237
  84. W. H. Stevens, On the homology of branched cyclic covers of knots, PhD thesis, Louisiana State Univ. and Agricultural & Mechanical College, 1996, 40 pp.
  85. Weigang Sun, Shuai Wang, Jingyuan Zhang, “Counting spanning trees in prism and anti-prism graphs”, J. Appl. Anal. Comput., 6:1 (2016), 65–75
  86. L. Takacs, “On the number of distinct forests”, SIAM J. Discrete Math., 3:4 (1990), 574–581
  87. H. N. V. Templerley, M. E. Fisher, “Dimer problem in statistical mechanics – an exact result”, Philos. Mag. (8), 6:68 (1961), 1061–1063
  88. L. Weinberg, “Number of trees in a graph”, Proc. IRE, 46:12 (1958), 1954–1955
  89. H. Wiener, “Structural determination of paraffin boiling points”, J. Amer. Chem. Soc., 69:1 (1947), 17–20
  90. F. Y. Wu, “Number of spanning trees on a lattice”, J. Phys. A, 10:6 (1977), L113–L115
  91. Wenjun Xiao, I. Gutman, “Resistance distance and Laplacian spectrum”, Theor. Chem. Acc., 110 (2003), 284–289
  92. Heping Zhang, Yujun Yang, “Resistance distance and Kirchhoff index in circulant graphs”, Int. J. Quantum Chem., 107:2 (2007), 330–339
  93. Yuanping Zhang, Xuerong Yong, M. J. Golin, “The number of spanning trees in circulant graphs”, Discrete Math., 223:1-3 (2000), 337–350
  94. Yuanping Zhang, Xuerong Yong, M. J. Golin, “Chebyshev polynomials and spanning tree formulas for circulant and related graphs”, Discrete Math., 298:1-3 (2005), 334–364
  95. H.-Y. Zhu, D. J. Klein, I. Lukovits, “Extensions of the Wiener number”, J. Chem. Inf. Comput. Sci., 36:3 (1996), 420–428

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2023 Mednykh A.D., Mednykh I.A.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».