On the Jacobian group of a cone over a circulant graph

Liliya A. Grunwald; Ilya A. Mednykh

doi:10.25587/SVFU.2021.32.84.006

Grunwald Liliya A., lfb_o@yahoo.co.uk Sobolev Institute of Mathematics, 4 Koptyug Avenue, Novosibirsk 630090, Russia; Novosibirsk State University, 1 Pirogov Street, Novosibirsk 630090, Russia https://orcid.org/0000-0003-4622-5259
Mednykh Ilya A., ilyamednykh@mail.ru Sobolev Institute of Mathematics, 4 Koptyug Avenue, Novosibirsk 630090, Russia; Novosibirsk State University, 1 Pirogov Street, Novosibirsk 630090, Russia https://orcid.org/0000-0001-7682-3917

DOI: https://doi.org/10.25587/SVFU.2021.32.84.006

Keywords: spanning tree, spanning forest, circulant graph, Laplacian matrix, cone over graph, Chebyshev polynomial

Abstract

For any given graph G, consider the graph Ĝ which is a cone over G. We study two important invariants of such a cone, namely, the complexity (the number of spanning trees) and the Jacobian of the graph. We prove that complexity of graph Ĝ coincides with the number of rooted spanning forests in G and the Jacobian of Ĝ is isomorphic to the cokernel of the operator I + L(G), where L(G) is the Laplacian of G and I is the identity matrix. As a consequence, one can calculate the complexity of Ĝ as det(I + L(G)).

As an application, we establish general structural theorems for the Jacobian of Ĝ in the case when G is a circulant graph or cobordism of two circulant graphs.

References

[1]
Cayley A., “A theorem on trees,” Q. J. Pure Appl. Math., 23, 376–378 (1889).

[2]
Boesch F. T. and Prodinger H., “Spanning tree formulas and Chebyshev polynomials,” Graphs Comb., 2, No. 1, 191–200 (1986).

[3]
Hilton A. J. W., “Spanning trees and Fibonacci and Lucas numbers,” Fibonacci Q., 12, 259–262 (1974).

[4]
Sedlácěk J., “On the spanning trees of finite graphs,” ˇ Cas. Pěstování Mat., 94, 217–221 (1969).

[5]
Sedlácěk J., “On the skeletons of a graph or digraph,” in: Combinatorial Structures and Their Applications (R. Guy, M. Hanani, N. Saver, J. Schonheim, eds.), pp. 387–391, Gordon and Breach, New York (1970).

[6]
Shrock R. and Wu F. Y., “Spanning trees on graphs and lattices in d-dimensions,” J. Phys. A, 33, 3881–3902 (2000).

[7]
Boesch F. T. and Bogdanowicz Z. R., “The number of spanning trees in a prism,” Int. J. Comput. Math., 21, 229–243 (1987).

[8]
Sun W., Wang S., and Zhang J., “Counting spanning trees in prism and anti-prism graphs,” J. Appl. Anal. Comput., 6, 65–75 (2016).

[9]
Kirchhoff G., “Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird,” Ann. Phys. Chem., 72, 497–508 (1847).

[10]
Kel’mans A. K. and Chelnokov V. M., “A certain polynomial of a graph and graphs with an extremal number of trees,” J. Comb. Theory, Ser. B, 1, 197–214 (1974).

[11]
Knill O., “Counting rooted forests in a network,” arXiv.org e-Print archive, arXiv:1307.3810, 18 Jul 2013.

[12]
Jin Y. and Lin C., “Enumeration for spanning forests of complete bipartite graphs,” Ars Comb., 70, 135–138 (2004).

[13]
Sung S. U., “Enumeration for spanning trees and forests of join graphs based on the combinatorial decomposition,” Electron. J. Graph Theory Appl., 4, No. 2, 171–177 (2016).

[14]
Grunwald L. and Mednykh I., “The number of rooted forests in circulant graphs,” arXiv.org e-Print archive, arXiv:1907.02635 [math.CO], 2019.

[15]
Calan D., “A combinatorial derivation of the number of labeled forests,” J. Integer Seq., 6, No. 4, 03.4.7, 1–3 (2003).

[16]
Liu C. J. and Chow Y., “Enumeration of forests in a graph,” Proc. Amer. Math. Soc., 83, 659–662 (1981).

[17]
Takács L., “On the number of distinct forests,” SIAM J. Discrete Math., 3, No. 4, 574–581 (1990).

[18]
Cori R. and Rossin D., “On the sandpile group of dual graphs,” Eur. J. Comb., 21, No. 4, 447–459 (2000).

[19]
Baker B. and Norine S., “Harmonic morphisms and hyperelliptic graphs,” Int. Math. Res. Notes, 15, 2914–2955 (2009).

[20]
Biggs N. L., “Chip-firing and the critical group of a graph,” J. Algebr. Comb., 9, No. 1, 25–45 (1999).

[21]
Bacher R., de la Harpe P., and Nagnibeda T., “The lattice of integral flows and the lattice of integral cuts on a finite graph,” Bull. Soc. Math. France, 125, 167–198 (1997).

[22]
Alfaro C. A. and Valencia E., “On the sandpile group of the cone of a graph,” Linear Algebra Appl., 436, No. 5, 1154–1176 (2012).

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

[24]
Lorenzini D., “Smith normal form and Laplacians,” J. Comb. Theory, Ser. B., 98, No. 6, 1271–1300 (2008).

[25]
Hou Y., Woo Ch., and Chen P., “On the sandpile group of the square cycle,” Linear Algebra Appl., 418, 457–467 (2006).

[26]
Chen P. and Hou Y., “On the critical group of the Möbius ladder graph,” Aust. J. Comb., 36, 133–142 (2006).

[27]
Mednykh I. A. and Zindinova M. A., “On the structure of Picard group for Möebius ladder,” Sib. Elektron. Mat. Izv., 8, 54–61 (2011).

[28]
Mednykh A. D. and Mednykh I. A., “On the structure of the Jacobian group for circulant graphs,” Dokl. Math., 94, No. 1, 445–449 (2016).

[29]
Mednykh I. A., “On Jacobian group and complexity of I-graph I(n, k, l) through Chebyshev polynomials,” Ars Math. Contemp., 15, 467–485 (2018).

[30]
Davis P. J., Circulant Matrices, AMS Chelsea Publ. (1994).

[31]
Chebotarev P. and Shamis E., “Matrix forest theorems,” arXiv.org e-Print archive, arXiv: math/0602575 [math.CO], 2006.

[32]
Kel’mans A. K., “The number of trees in a graph, I,” Autom. Remote Control, 26, 2118–2129 (1965).

[33]
Kel’mans A. K., “The number of trees in a graph, II,” Autom. Remote Control, 27, 233–241 (1966).

[34]
Mohar B., “The Laplacian spectrum of graphs,” in: Graph Theory, Combinatorics, and Applications, vol. 2 (Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk, eds.), pp. 871–898, Wiley (1991).

[35]
Abrosimov N. V., Baigonakova G. A., and Mednykh I. A., “Counting spanning trees in cobordism of two circulant graphs,” Sib. Elektron. Mat. Izv., 15, 1145–1157 (2018).