×

The structure of sandpile groups of outerplanar graphs. (English) Zbl 1478.05029

Appl. Math. Comput. 395, Article ID 125861, 16 p. (2021); corrigendum ibid. 398, Article ID 126022, 2 p. (2021).
Summary: We compute the sandpile groups of families of planar graphs having a common weak dual by evaluating the indeterminates of the critical ideals of the weak dual at the lengths of the cycles bounding the interior faces. This method allows us to determine the algebraic structure of the sandpile groups of outerplanar graphs, and can be used to compute the sandpile groups of many other planar graph families. Finally, we compute the identity element for the sandpile groups of the dual graphs of many outerplane graphs.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05E18 Group actions on combinatorial structures
13F20 Polynomial rings and ideals; rings of integer-valued polynomials
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Software:

SageMath
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Abiad, C. A. Alfaro, K. Heysse, M. C. Vargas, Eigenvalues, smith normal form and determinantal ideals. Preprint arXiv:1910.12502.
[2] Alfaro, C. A., On the sandpile group of a graph (2010), CINVESTAV-IPN, Mexico, Master thesis
[3] Alfaro, C. A.; Lin, J. C.H., Critical ideals, minimum rank and zero forcing number, Appl. Math. Comput., 358, 305-313 (2019) · Zbl 1428.05128
[4] Alfaro, C. A.; Taylor, L., Distance ideals of graphs, Linear Algebra Appl., 584, 127-144 (2020) · Zbl 1426.05060
[5] Alfaro, C. A.; Valencia, C. E., On the sandpile group of the cone of a graph, Linear Algebra Appl., 436, 1154-1176 (2012) · Zbl 1236.05131
[6] C.A. Alfaro, C.E. Valencia, M.C. Vargas, Computing sandpile configurations using integer linear programming. Preprint arXiv:2008.13672.
[7] Alfaro, C. A.; Corrales, H. H.; Valencia, C. E., Critical ideals of signed graphs with twin vertices, Adv. in Appl. Math., 86, 99-131 (2017) · Zbl 1391.13036
[8] Bacher, R.; de la Harpe, P.; 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) · Zbl 0891.05062
[9] Bak, P.; Tang, C.; Wiesenfeld, K., Self-organized criticallity: an explanation of \(1/f\) noise, Phys. Rev. Lett., 59, 381-384 (1987)
[10] Becker, R.; Glass, D. B., Cyclic critical groups of graphs, Australas. J. Combin., 64, 366-375 (2016) · Zbl 1333.05254
[11] Berman, K. A., Bicycles and spanning trees, SIAM J. Algebr. Discrete Methods, 7, 1-12 (1986) · Zbl 0588.05016
[12] Biggs, N., Chip-firing and the critical group of a graph, J. Algebraic Combin., 9, 25-45 (1999) · Zbl 0919.05027
[13] Bondy, J. A.; Murty, U. S.R., Graph Theory, Grad, Texts in Math., vol. 244 (2008), Springer · Zbl 1134.05001
[14] Buchanan, M., Ubiquity: Why Catastrophes Happen, 273 pp. (2000), Three Rivers Press: Three Rivers Press New York
[15] Chen, S.; Ye, S. K., Critical groups for homeomorphism classes of graphs, Discrete Math., 309, 255-258 (2009) · Zbl 1198.05088
[16] Chen, H.; Mohar, B., The sandpile group of a polygon flower, Discrete Appl. Math., 270, 68-82 (2019) · Zbl 1426.05015
[17] Comellas, F.; Miralles, A.; Liu, H.; Zhang, Z., The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs, Phys. A, 392, 2803-2806 (2013) · Zbl 1395.05157
[18] Cori, R.; Rossin, D., On the sandpile group of dual graphs, European J. Combin., 21, 447-459 (2000) · Zbl 0969.05034
[19] Corrales, H.; Valencia, C. E., On the critical ideals of graphs, Linear Algebra Appl., 439, 3870-3892 (2013) · Zbl 1295.13028
[20] H. Corrales, C.E. Valencia, Critical ideals of trees. Preprint arXiv:1504.06239. · Zbl 1295.13028
[21] Corry, S.; Perkinson, D., Divisors and sandpiles, An introduction to chip-firing (2018), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1411.05003
[22] Fleischner, H. J.; Geller, D. P.; Harary, F., Outerplanar graphs and weak duals, J. Indian Math. Soc. (N.S.), 38, 215-219 (1974) · Zbl 0352.05029
[23] Gao, Y., On the critical ideals of complete multipartite graphs, Electron. J. Linear Algebra, 36, 94-105 (2020) · Zbl 1437.13038
[24] Johnson, C. R.; Saiago, C. M., Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of the matrix, Electron. J. Linear Algebra, 9, 27-31 (2002) · Zbl 0999.15005
[25] Klivans, C. J., The Mathematics of Chip-Firing (2018), CRC Press, Taylor & Francis Group · Zbl 1403.05003
[26] Krepkiy, I. A., The sandpile groups of chain-cyclic graphs, J. Math. Sci., 200, 698-709 (2014) · Zbl 1307.05107
[27] Liao, Y.; Fang, A.; Hou, Y., The tutte polynomial of an infinite family of outerplanar, small-world and self-similar graphs, Phys. A, 392, 4584-4593 (2013) · Zbl 1395.05084
[28] Lorenzini, D. J., Smith normal form and laplacians, J. Combin. Theory B, 98, 1271-1300 (2008) · Zbl 1175.05088
[29] Merino, C., The chip-firing game, Discrete Math., 302, 188-210 (2005) · Zbl 1139.91314
[30] Merris, R., Unimodular equivalence of graphs, Linear Algebra Appl., 173, 181-189 (1992) · Zbl 0763.05071
[31] Phifer, C. R., The cycle intersection matrix and applications to planar graphs and data analysis for postsecondary mathematics education, 73 pp (2014), University of Rhode Island, Thesis (ph.d.)
[32] The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.0), 2017. Available at http://www.sagemath.org.
[33] Stanley, R. P., Smith normal form in combinatorics, J. Combin. Theory A, 144, 476-495 (2016) · Zbl 1343.05026
[34] Vince, A., Elementary divisors of graphs and matroids, Europ. J. Combinat., 12, 445-453 (1991) · Zbl 0762.05033
[35] D.G. Wagner, The critical group of a directed graph. Preprint arXiv:math/0010241v1.
[36] Watkins, W., The laplacian matrix of a graph: unimodular congruence, Linear Multil. Algebra, 28, 35-43 (1990) · Zbl 0744.05032
[37] Wood, M. M., The distribution of sandpile groups of random graphs, J. Amer. Math. Soc., 30, 915-958 (2017) · Zbl 1366.05098
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.