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

A. D. Mednykh   ; I. A. Mednykh

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 78 (2023) no. 3, pp. 501-548

Résumé

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. Bibliography: 95 titles.

Détail

Keywords: graph, Abelian group, spanning trees, rooted spanning forests, Kirchhoff index, Fibonacci numbers, Chebyshev polynomials.
Mots-clés : Jacobian

Bibliographie

[1] N. V. Abrosimov, G. A. Baigonakova, L. A. Grunwald, and I. A. Mednykh, “Counting rooted spanning forests in cobordism of two circulant graphs”, Sib. Èlektron. Mat. Izv., 17 (2020), 814–823 | DOI | MR | Zbl

[2] N. V. Abrosimov, G. A. Baigonakova, and I. A. Mednykh, “Counting spanning trees in cobordism of two circulant graphs”, Sib. Èlektron. Mat. Izv., 15 (2018), 1145–1157 | DOI | MR | Zbl

[3] A. Ádám, “Research problem 2-10”, J. Combin. Theory, 2 (1967), 393

[4] R. Bacher, P. de la Harpe, and 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 | DOI | MR | Zbl

[5] G. A. Baigonakova avd A. D. Mednykh, “Elementary formulas for Kirchhoff index of Möbius ladder and prism graphs”, Sib. Èlektron. Mat. Izv., 16 (2019), 1654–1661 | DOI | MR | Zbl

[6] M. Baker and S. Norine, “Harmonic morphisms and hyperelliptic graphs”, Int. Math. Res. Not. IMRN, 2009:15 (2009), 2914–2955 | DOI | MR | Zbl

[7] H. Bass, “Covering theory for graphs of groups”, J. Pure Appl. Algebra, 89:1-2 (1993), 3–47 | DOI | MR | Zbl

[8] N. Biggs, “Three remarkable graphs”, Canad. J. Math., 25:2 (1973), 397–411 | DOI | MR | Zbl

[9] N. L. Biggs, “Chip-firing and the critical group of a graph”, J. Algebraic Combin., 9:1 (1999), 25–45 | DOI | MR | Zbl

[10] F. T. Boesch and Z. R. Bogdanowicz, “The number of spanning tress in a prism”, Internat. J. Comput. Math., 21:3-4 (1987), 229–243 | DOI

[11] F. T. Boesch and H. Prodinger, “Spanning tree formulas and Chebyshev polynomials”, Graphs Combin., 2 (1986), 191–200 | DOI | MR | Zbl

[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 | MR | Zbl

[13] D. Calan, “A combinatorial derivation of the number of labeled forests”, J. Integer Seq., 6:4 (2003), 03.4.7, 9 pp. | MR | Zbl

[14] P. Chebotarev, “Spanning forests and the golden ratio”, Discrete Appl. Math., 156:5 (2008), 813–821 | DOI | MR | Zbl

[15] P. Chebotarev and R. Agaev, “Forest matrices around the Laplacian matrix”, Linear Algebra Appl., 356:1-3 (2002), 253–274 | DOI | MR | Zbl

[16] P. Chebotarev and E. Shamis, Matrix-forest theorems, 2006, 10 pp., arXiv: math/0602575

[17] Pingge Chen, Yaoping Hou, and Chingwah Woo, “On the critical group of the Möbius ladder graph”, Australas. J. Combin., 36 (2006), 133–142 | MR | Zbl

[18] Xiebin Chen, Qiuying Lin, and Fuji Zhang, “The number of spanning trees in odd valent circulant graphs”, Discrete Math., 282:1-3 (2004), 69–79 | DOI | MR | Zbl

[19] Z. Cinkir, “Effective resistances and Kirchhoff index of ladder graphs”, J. Math. Chem., 54:4 (2016), 955–966 | DOI | MR | Zbl

[20] Z. Cinkir, Effective resistances and Kirchhoff index of prism graphs, 2017, 9 pp., arXiv: 1704.03429

[21] M. Conder and R. Grande, “On embeddings of circulant graphs”, Electron. J. Combin., 22:2 (2015), P2.28, 27 pp. | DOI | MR | Zbl

[22] R. Cori and D. Rossin, “On the sandpile group of dual graphs”, European J. Combin., 21:4 (2000), 447–459 | DOI | MR | Zbl

[23] P. J. Davis, Circulant matrices, 2nd ed., AMS Chelsea Publishing, New York, NY, 1994 | MR | Zbl

[24] D. Dhar, P. Ruelle, S. Sen, and D.-N. Verma, “Algebraic aspects of Abelian sandpile models”, J. Phys. A: Math. Gen., 28:4 (1995), 805–831 | DOI | MR | Zbl

[25] S. A. Evdokimov and I. N. Ponomarenko, “Circulant graphs: recognizing and isomorphism testing in polynomial time”, St. Petersburg Math. J., 15:6 (2004), 813–835 | DOI | MR | Zbl

[26] G. Everest and T. Ward, Heights of polynomials and entropy in algebraic dynamics, Universitext, Springer-Verlag London, Ltd., London, 2013, 212 pp. | DOI | MR | Zbl

[27] C. Godsil and G. Royle, Algebraic graph theory, Grad. Texts in Math., 207, Springer-Verlag, New York, 2001, xx+439 pp. | DOI | MR | Zbl

[28] G. Goel and D. Perkinson, “Critical groups of iterated cones”, Linear Algebra Appl., 567 (2019), 138–142 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[30] J. L. Gross and T. W. Tucker, Topological graph theory, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley Sons, Inc., New York, 1987, xvi+351 pp. | MR | Zbl

[31] L. A. Grunwald, Young Soo Kwon, and I. A. Mednykh, “Counting rooted spanning forests for circulant foliation over a graph”, Tohoku Math. J. (2), 74:4 (2022), 535–548 | DOI | MR | Zbl

[32] L. A. Grunwald and I. A. Mednykh, “On the Jacobian group of a cone over a circulant graph”, Mat. Zametki Sev. Vost. federal. Univ., 28:2 (2021), 88–101 | DOI

[33] L. A. Grunwald and I. A. Mednykh, “The number of rooted forests in circulant graphs”, Ars Math. Contemp., 22:4 (2022), 10, 12 pp. | DOI | MR | Zbl

[34] I. Gutman and B. Mohar, “The quasi-Wiener and the Kirchhoff indices coincide”, J. Chem. Inf. Comput. Sci., 36:5 (1996), 982–985 | DOI

[35] A. J. Guttmann and M. D. Rogers, “Spanning tree generating functions and Mahler measures”, J. Phys. A, 45:49 (2012), 494001, 24 pp. | DOI | MR | Zbl

[36] A. J. W. Hilton, “Spanning trees and Fibonacci and Lucas numbers”, Fibonacci Quart., 12 (1974), 259–262 | MR | Zbl

[37] J. D. Horton and I. Z. Bouwer, “Symmetric $Y$-graphs and $H$-graphs”, J. Combin. Theory Ser. B, 53:1 (1991), 114–129 | DOI | MR | Zbl

[38] Yaoping Hou, Chingwah Woo, and Pingge Chen, “On the sandpile group of the square cycle $C_n^2$”, Linear Algebra Appl., 418:2-3 (2006), 457–467 | DOI | MR | Zbl

[39] Danrun Huang, “A cyclic six-term exact sequence for block matrices over a PID”, Linear Multilinear Algebra, 49:2 (2001), 91–114 | DOI | MR | Zbl

[40] B. Jacobson, A. Niedermaier, and V. Reiner, “Critical groups for complete multipartite graphs and Cartesian products of complete graphs”, J. Graph Theory, 44:3 (2003), 231–250 | DOI | MR | Zbl

[41] J. L. V. W. Jensen, “Sur un nouvel et important théorème de la théorie des fonctions”, Acta Math., 22:1 (1899), 359–364 | DOI | MR | Zbl

[42] Yinglie Jin and Chunlin Lin, “Enumeration for spanning forests of complete bipartite graphs”, Ars Combin., 70 (2004), 135–138 | MR | Zbl

[43] M. Kagan and B. Mata, “A physics perspective on the resistance distance for graphs”, Math. Comput. Sci., 13:1-2 (2019), 105–115 | DOI | MR | Zbl

[44] A. K. Kelmans and 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 | DOI | MR | Zbl

[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 | DOI

[46] D. J. Klein and M. Randić, “Resistance distance”, J. Math. Chem., 12:1-4 (1993), 81–95 | DOI | MR

[47] O. Knill, “Cauchy–Binet for pseudo-determinants”, Linear Algebra Appl., 459 (2014), 522–547 | DOI | MR | Zbl

[48] M. Kotani and T. Sunada, “Jacobian tori associated with a finite graph and its Abelian covering graphs”, Adv. in Appl. Math., 24:2 (2000), 89–110 | DOI | MR | Zbl

[49] Y. S. Kwon, A. D. Mednykh, and 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 | DOI | MR | Zbl

[50] Y. S. Kwon, A. D. Mednykh, and I. A. Mednykh, On complexity of cyclic coverings of graphs, 2018, 19 pp., arXiv: 1811.03801

[51] Y. S. Kwon, A. D. Mednykh, and I. A. Mednykh, “Complexity of the circulant foliation over a graph”, J. Algebraic Combin., 53:1 (2021), 115–129 | DOI | MR | Zbl

[52] D. H. Lehmer, “Factorization of certain cyclotomic functions”, Ann. of Math. (2), 34:3 (1933), 461–479 | DOI | MR | Zbl

[53] C. J. Liu and Yutze Chow, “Enumeration of forests in a graph”, Proc. Amer. Math. Soc., 83:3 (1981), 659–662 | DOI | MR | Zbl

[54] D. Lorenzini, “Smith normal form and Laplacians”, J. Combin. Theory Ser. B, 98:6 (2008), 1271–1300 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[56] I. Lukovits, S. Nikolić, and N. Trinajstić, “Resistance distance in regular graphs”, Int. J. Quantum Chem., 71:3 (1999), 217–225 | 3.0.CO;2-C class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[57] Ye Luzhen, “On the Kirchhoff index of some toroidal lattices”, Linear Multilinear Algebra, 59:6 (2011), 645–650 | DOI | MR | Zbl

[58] K. Mahler, “On some inequalities for polynomials in several variables”, J. London Math. Soc., 37 (1962), 341–344 | DOI | MR | Zbl

[59] W. S. Massey, Algebraic topology: an introduction, Harcourt, Brace World, Inc., New York, 1967, xix+261 pp. ; J. Stallings, Group theory and three-dimensional manifolds, Yale Math. Monogr., 4, Yale Univ. Press, New Haven, CT–London, 1971, v+65 pp. | MR | Zbl | MR | Zbl

[60] A. D. Mednykh and I. A. Mednykh, “On the structure of the Jacobian group for circulant graphs”, Dokl. Math., 94:1 (2016), 445–449 | DOI | MR | Zbl

[61] A. D. Mednykh and I. A. Mednykh, “Asymptotics and arithmetical properties of complexity for circulant graphs”, Dokl. Math., 97:2 (2018), 147–151 | DOI | MR | Zbl

[62] A. D. Mednykh and I. A. Mednykh, “The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic”, Discrete Math., 342:6 (2019), 1772–1781 | DOI | MR | Zbl

[63] A. D. Mednykh and I. A. Mednykh, “On the structure of the critical group of a circulant graph with non-constant jumps”, Russian Math. Surveys, 75:1 (2020), 190–192 | DOI | MR | Zbl

[64] A. D. Mednykh and I. A. Mednykh, “Kirchhoff index for circulant graphs and its asymptotics”, Dokl. Math., 102:2 (2020), 392–395 | DOI | MR | Zbl

[65] A. D. Mednykh and I. A. Mednykh, “On rationality of generating function for the number of spanning trees in circulant graphs”, Algebra Colloq., 27:1 (2020), 87–94 | DOI | MR | Zbl

[66] A. D. Mednykh and I. A. Mednykh, “Plans' periodicity theorem for Jacobian of circulant graphs”, Dokl. Math., 103:3 (2021), 139–142 | DOI | MR | Zbl

[67] A. Mednykh and I. Mednykh, “Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics”, Ars Math. Contemp., 23:1 (2023), 8, 16 pp. | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[69] I. A. Mednykh and M. A. Zindinova, “On the structure of Picard group for Moebius ladder”, Sib. Èlektron. Mat. Izv., 8 (2011), 54–61 | MR | Zbl

[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 | MR | Zbl

[71] M. Muzychuk, “A solution of the isomorphism problem for circulant graphs”, Proc. London Math. Soc. (3), 88:1 (2004), 1–41 | DOI | MR | Zbl

[72] N. Neumärker, The arithmetic structure of discrete dynamical systems on the torus, PhD thesis, Univ. Bielefeld, Bielefeld, 2012, 92 pp., pp. https://pub.uni-bielefeld.de/download/2508475/2508565/Diss_Neumaerker.pdf

[73] J. L. Palacios, “Closed-form formulas for Kirchhoff index”, Int. J. Quantum Chem., 81:2 (2001), 135–140 | 3.0.CO;2-G class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[74] A. Plans, “Aportación al estudio de los grupos de homología de los recubrimientos cíclicos ramificados correspondientes a un nudo”, Rev. Acad. Ci. Madrid, 47 (1953), 161–193 | MR | Zbl

[75] V. V. Prasolov, Polynomials, Algorithms Comput. Math., 11, Springer-Verlag, Berlin, 2004, xiv+301 pp. | DOI | MR | Zbl

[76] M. Sakuma, “Homology of Abelian coverings of links and spatial graphs”, Canad. J. Math., 47:1 (1995), 201–224 | DOI | MR | Zbl

[77] J. Sedláček, “On the number of spanning trees of finite graphs”, Časopis Pěst. Mat., 94:2 (1969), 217–221 | MR | Zbl

[78] J. Sedlácě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 | MR | Zbl

[79] R. Shrock and F. Y. Wu, “Spanning trees on graphs and lattices in $d$ dimensions”, J. Phys. A, 33:21 (2000), 3881–3902 | DOI | MR | Zbl

[80] D. S. Silver and S. G. Williams, Spanning trees and Mahler measure, 2016, 12 pp., arXiv: 1602.02797

[81] D. S. Silver and S. G. Williams, Graph complexity and Mahler measure, 2017, 16 pp., arXiv: 1701.06097

[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 | DOI | MR | Zbl

[83] A. Steimle and W. Staton, “The isomorphism classes of the generalized Petersen graphs”, Discrete Math., 309:1 (2009), 231–237 | DOI | MR | Zbl

[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. | DOI | MR

[85] Weigang Sun, Shuai Wang, and Jingyuan Zhang, “Counting spanning trees in prism and anti-prism graphs”, J. Appl. Anal. Comput., 6:1 (2016), 65–75 | DOI | MR | Zbl

[86] L. Takács, “On the number of distinct forests”, SIAM J. Discrete Math., 3:4 (1990), 574–581 | DOI | MR | Zbl

[87] H. N. V. Templerley and M. E. Fisher, “Dimer problem in statistical mechanics – an exact result”, Philos. Mag. (8), 6:68 (1961), 1061–1063 | DOI | MR | Zbl

[88] L. Weinberg, “Number of trees in a graph”, Proc. IRE, 46:12 (1958), 1954–1955 | DOI

[89] H. Wiener, “Structural determination of paraffin boiling points”, J. Amer. Chem. Soc., 69:1 (1947), 17–20 | DOI

[90] F. Y. Wu, “Number of spanning trees on a lattice”, J. Phys. A, 10:6 (1977), L113–L115 | DOI | MR

[91] Wenjun Xiao and I. Gutman, “Resistance distance and Laplacian spectrum”, Theor. Chem. Acc., 110 (2003), 284–289 | DOI

[92] Heping Zhang and Yujun Yang, “Resistance distance and Kirchhoff index in circulant graphs”, Int. J. Quantum Chem., 107:2 (2007), 330–339 | DOI

[93] Yuanping Zhang, Xuerong Yong, and M. J. Golin, “The number of spanning trees in circulant graphs”, Discrete Math., 223:1-3 (2000), 337–350 | DOI | MR | Zbl

[94] Yuanping Zhang, Xuerong Yong, and M. J. Golin, “Chebyshev polynomials and spanning tree formulas for circulant and related graphs”, Discrete Math., 298:1-3 (2005), 334–364 | DOI | MR | Zbl

[95] H.-Y. Zhu, D. J. Klein, and I. Lukovits, “Extensions of the Wiener number”, J. Chem. Inf. Comput. Sci., 36:3 (1996), 420–428 | DOI