Finiteness thresholds and surface bounds for graph Jacobians

Nifa, Anass

doi:10.5281/zenodo.23622186

Preprint · v3

Finiteness thresholds and surface bounds for graph Jacobians

Anass NifaPublished: 29 September 2026Updated: 24 October 2026

Read free PDF Read on Zenodo Zenodo record

Free PDF · 20 pages · 0.71 MB

Abstract

For a finite connected graph $G$ , let $e(G)$ be the exponent of its Jacobian and $\Delta(G)$ its maximum degree. For each integer $b\ge1$ , the simple biconnected graphs with $e(G)\le b$ form finitely many isomorphism classes if and only if $b\le7$ ; exactly eleven occur with $e(G)\le7$ . The simple biconnected graphs with $e(G)-\Delta(G)\le3$ are $K_n$ ( $n\ge3$ ), $C_4$ , $C_5$ and $K_{2,3}$ . At exponent eight, the number of vertices is unbounded among simple planar bipartite biconnected graphs of maximum degree four. For every integer $r\ge1$ , there is a simple planar biconnected graph whose Jacobian is isomorphic to $(\mathbb Z/8\mathbb Z)^r$ , with explicit divisor generators and an orthogonal decomposition of its monodromy pairing. Every simple $3$ -connected planar graph satisfies $2|V(G)|-4\le(e(G)-\Delta(G)+1)^2$ and $2|V(G)|-5\le3e(G)^2/5$ . Every simple graph with a cellular torus embedding whose full inverse image in the universal cover of the torus is $3$ -connected satisfies $|V(G)|\le e(G)^2$ .

MSC 2020

05C25: Graphs and abstract algebra (groups, rings, fields, etc.)
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C10: Planar graphs; geometric and topological aspects of graph theory
05C40: Connectivity
20K01: Finite abelian groups

Mathematics Subject Classification 2020

Record

Version DOI: 10.5281/zenodo.23622186
All versions: 10.5281/zenodo.22859832
Subjects: Graph Jacobian; exponent; biconnected graph; integral potential; monodromy pairing; planar graph; toroidal embedding
Language: English

Cite this paper

Anass Nifa. Finiteness thresholds and surface bounds for graph Jacobians. Preprint, Zenodo, v3 (2026). doi:10.5281/zenodo.23622186

Download BibTeX Download RIS

References

As listed in the manuscript bibliography.

[1]
A. Azimi, R. B. Bapat and M. Farrokhi D. G., Resistance distance of blowups of trees, Discrete Math. 344 (2021), no. 7, Article 112387. 10.1016/j.disc.2021.112387.
DOI
[2]
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 (1997), no. 2, 167–198. 10.24033/bsmf.2303.
DOI
[3]
M. Baker and F. Shokrieh, Chip-firing games, potential theory on graphs, and spanning trees, J. Combin. Theory Ser. A 120 (2013), no. 1, 164–182. 10.1016/j.jcta.2012.07.011.
DOI
[4]
M. Beck and S. Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, second ed., Undergraduate Texts in Mathematics, Springer, New York, 2015. 10.1007/978-1-4939-2969-6.
DOI
[5]
N. Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29 (1997), no. 6, 641–682. 10.1112/S0024609397003305.
DOI
[6]
D. Brandfonbrener, P. Devlin, N. Friedenberg, Y. Ke, S. Marcus, H. Reichard and E. Sciamma, Two-vertex generators of Jacobians of graphs, Electron. J. Combin. 25 (2018), no. 1, P1.15, 18 pp. 10.37236/7302.
DOI
[7]
Y. Colin de Verdière, Comment rendre géodésique une triangulation d’une surface?, Enseign. Math. (2) 37 (1991), nos. 3–4, 201–212.
[8]
R. Diestel, Graph Theory, fifth ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017. 10.1007/978-3-662-53622-3.
DOI
[9]
F. Dörfler and F. Bullo, Kron reduction of graphs with applications to electrical networks, IEEE Trans. Circuits Syst. I 60 (2013), no. 1, 150–163. 10.1109/TCSI.2012.2215780.
DOI
[10]
X. Dong, W. Guo and G. Jiang, On the critical group of the k-partite graph, preprint (2024), arXiv:2409.02654v1.
arXiv v1
[11]
J. Erickson and P. Lin, A toroidal Maxwell–Cremona–Delaunay correspondence, J. Comput. Geom. 12 (2021), no. 2, 55–85. 10.20382/jocg.v12i2a4.
DOI
[12]
L. Gaudet, D. Jensen, D. Ranganathan, N. Wawrykow and T. Weisman, Realization of groups with pairing as Jacobians of finite graphs, Ann. Comb. 22 (2018), no. 4, 781–801. 10.1007/s00026-018-0406-0.
DOI
[13]
Q. Huang, H. Chen and Q. Deng, Resistance distances and the Kirchhoff index in double graphs, J. Appl. Math. Comput. 50 (2016), 1–14. 10.1007/s12190-014-0855-5.
DOI
[14]
B. Jacobson, A. Niedermaier and V. Reiner, Critical groups for complete multipartite graphs and Cartesian products of complete graphs, J. Graph Theory 44 (2003), no. 3, 231–250. 10.1002/jgt.10139.
DOI
[15]
H. Liu, L. Li, L. You, H. Hua and L. Chen, Enumeration of spanning trees and resistance distances of generalized blow-up graphs, Discrete Appl. Math. 381 (2026), 276–291. 10.1016/j.dam.2025.11.014. arXiv:2504.15314v1 (2025).
DOI · arXiv v1
[16]
H. Lheem, D. Li, C. J. Quines and J. Zhang, Exponents of Jacobians of graphs and regular matroids, Rose-Hulman Undergrad. Math. J. 21 (2020), no. 2, Article 6. arXiv:1910.06442v2 (2021).
arXiv v2
[17]
D. Lorenzini, A finite group attached to the Laplacian of a graph, Discrete Math. 91 (1991), no. 3, 277–282. 10.1016/0012-365X(90)90236-B.
DOI
[18]
D. Lorenzini, Smith normal form and Laplacians, J. Combin. Theory Ser. B 98 (2008), no. 6, 1271–1300. 10.1016/j.jctb.2008.02.002.
DOI
[19]
R. Lyons and Y. Peres, Probability on Trees and Networks, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 42, Cambridge University Press, New York, 2016. 10.1017/9781316672815.
DOI
[20]
M. C. Marino and N. Zagaglia Salvi, Generalizing double graphs, Atti Accad. Peloritana Pericolanti Cl. Sci. Fis. Mat. Natur. 85 (2007), Article C1A0702002. 10.1478/C1A0702002.
DOI
[21]
E. Munarini, C. Perelli Cippo, A. Scagliola and N. Zagaglia Salvi, Double graphs, Discrete Math. 308 (2008), nos. 2–3, 242–254. 10.1016/j.disc.2006.11.038.
DOI
[22]
F. Shokrieh, The monodromy pairing and discrete logarithm on the Jacobian of finite graphs, J. Math. Cryptol. 4 (2010), no. 1, 43–56. 10.1515/JMC.2010.002.
DOI
[23]
W. Sun, Y. Yang and S.-J. Xu, Resistance distance and Kirchhoff index of unbalanced blowups of graphs, Discrete Math. 348 (2025), no. 3, Article 114327. 10.1016/j.disc.2024.114327.
DOI
[24]
Y. Tian and Y. Takane, Schur complements and Banachiewicz–Schur forms, Electron. J. Linear Algebra 13 (2005), 405–418. 10.13001/1081-3810.1171.
DOI
[25]
J. A. Tropp, ACM 204: Matrix Analysis, Caltech CMS Lecture Notes 2022-01, California Institute of Technology, Pasadena, 2022. 10.7907/m421-yb89.
DOI
[26]
W. T. Tutte, How to draw a graph, Proc. London Math. Soc. (3) 13 (1963), 743–767. 10.1112/plms/s3-13.1.743.
DOI
[27]
Y. Wang, D. Li and W. Yan, Resistance distance in blowup graphs, Discrete Math. 349 (2026), no. 2, Article 114765. 10.1016/j.disc.2025.114765.
DOI
[28]
S. Xu and K. Xu, Resistance distances in generalized join graphs, Discrete Appl. Math. 362 (2025), 18–33. 10.1016/j.dam.2024.11.013.
DOI

[reference-1] [1]
A. Azimi, R. B. Bapat and M. Farrokhi D. G., Resistance distance of blowups of trees, Discrete Math. 344 (2021), no. 7, Article 112387. 10.1016/j.disc.2021.112387.
DOI

[reference-2] [2]
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 (1997), no. 2, 167–198. 10.24033/bsmf.2303.
DOI

[reference-3] [3]
M. Baker and F. Shokrieh, Chip-firing games, potential theory on graphs, and spanning trees, J. Combin. Theory Ser. A 120 (2013), no. 1, 164–182. 10.1016/j.jcta.2012.07.011.
DOI

[reference-4] [4]
M. Beck and S. Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, second ed., Undergraduate Texts in Mathematics, Springer, New York, 2015. 10.1007/978-1-4939-2969-6.
DOI

[reference-5] [5]
N. Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29 (1997), no. 6, 641–682. 10.1112/S0024609397003305.
DOI

[reference-6] [6]
D. Brandfonbrener, P. Devlin, N. Friedenberg, Y. Ke, S. Marcus, H. Reichard and E. Sciamma, Two-vertex generators of Jacobians of graphs, Electron. J. Combin. 25 (2018), no. 1, P1.15, 18 pp. 10.37236/7302.
DOI

[reference-7] [7]
Y. Colin de Verdière, Comment rendre géodésique une triangulation d’une surface?, Enseign. Math. (2) 37 (1991), nos. 3–4, 201–212.

[reference-8] [8]
R. Diestel, Graph Theory, fifth ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017. 10.1007/978-3-662-53622-3.
DOI

[reference-9] [9]
F. Dörfler and F. Bullo, Kron reduction of graphs with applications to electrical networks, IEEE Trans. Circuits Syst. I 60 (2013), no. 1, 150–163. 10.1109/TCSI.2012.2215780.
DOI

[reference-10] [10]
X. Dong, W. Guo and G. Jiang, On the critical group of the k-partite graph, preprint (2024), arXiv:2409.02654v1.
arXiv v1

[reference-11] [11]
J. Erickson and P. Lin, A toroidal Maxwell–Cremona–Delaunay correspondence, J. Comput. Geom. 12 (2021), no. 2, 55–85. 10.20382/jocg.v12i2a4.
DOI

[reference-12] [12]
L. Gaudet, D. Jensen, D. Ranganathan, N. Wawrykow and T. Weisman, Realization of groups with pairing as Jacobians of finite graphs, Ann. Comb. 22 (2018), no. 4, 781–801. 10.1007/s00026-018-0406-0.
DOI

[reference-13] [13]
Q. Huang, H. Chen and Q. Deng, Resistance distances and the Kirchhoff index in double graphs, J. Appl. Math. Comput. 50 (2016), 1–14. 10.1007/s12190-014-0855-5.
DOI

[reference-14] [14]
B. Jacobson, A. Niedermaier and V. Reiner, Critical groups for complete multipartite graphs and Cartesian products of complete graphs, J. Graph Theory 44 (2003), no. 3, 231–250. 10.1002/jgt.10139.
DOI

[reference-15] [15]
H. Liu, L. Li, L. You, H. Hua and L. Chen, Enumeration of spanning trees and resistance distances of generalized blow-up graphs, Discrete Appl. Math. 381 (2026), 276–291. 10.1016/j.dam.2025.11.014. arXiv:2504.15314v1 (2025).
DOI · arXiv v1

[reference-16] [16]
H. Lheem, D. Li, C. J. Quines and J. Zhang, Exponents of Jacobians of graphs and regular matroids, Rose-Hulman Undergrad. Math. J. 21 (2020), no. 2, Article 6. arXiv:1910.06442v2 (2021).
arXiv v2

[reference-17] [17]
D. Lorenzini, A finite group attached to the Laplacian of a graph, Discrete Math. 91 (1991), no. 3, 277–282. 10.1016/0012-365X(90)90236-B.
DOI

[reference-18] [18]
D. Lorenzini, Smith normal form and Laplacians, J. Combin. Theory Ser. B 98 (2008), no. 6, 1271–1300. 10.1016/j.jctb.2008.02.002.
DOI

[reference-19] [19]
R. Lyons and Y. Peres, Probability on Trees and Networks, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 42, Cambridge University Press, New York, 2016. 10.1017/9781316672815.
DOI

[reference-20] [20]
M. C. Marino and N. Zagaglia Salvi, Generalizing double graphs, Atti Accad. Peloritana Pericolanti Cl. Sci. Fis. Mat. Natur. 85 (2007), Article C1A0702002. 10.1478/C1A0702002.
DOI

[reference-21] [21]
E. Munarini, C. Perelli Cippo, A. Scagliola and N. Zagaglia Salvi, Double graphs, Discrete Math. 308 (2008), nos. 2–3, 242–254. 10.1016/j.disc.2006.11.038.
DOI

[reference-22] [22]
F. Shokrieh, The monodromy pairing and discrete logarithm on the Jacobian of finite graphs, J. Math. Cryptol. 4 (2010), no. 1, 43–56. 10.1515/JMC.2010.002.
DOI

[reference-23] [23]
W. Sun, Y. Yang and S.-J. Xu, Resistance distance and Kirchhoff index of unbalanced blowups of graphs, Discrete Math. 348 (2025), no. 3, Article 114327. 10.1016/j.disc.2024.114327.
DOI

[reference-24] [24]
Y. Tian and Y. Takane, Schur complements and Banachiewicz–Schur forms, Electron. J. Linear Algebra 13 (2005), 405–418. 10.13001/1081-3810.1171.
DOI

[reference-25] [25]
J. A. Tropp, ACM 204: Matrix Analysis, Caltech CMS Lecture Notes 2022-01, California Institute of Technology, Pasadena, 2022. 10.7907/m421-yb89.
DOI

[reference-26] [26]
W. T. Tutte, How to draw a graph, Proc. London Math. Soc. (3) 13 (1963), 743–767. 10.1112/plms/s3-13.1.743.
DOI

[reference-27] [27]
Y. Wang, D. Li and W. Yan, Resistance distance in blowup graphs, Discrete Math. 349 (2026), no. 2, Article 114765. 10.1016/j.disc.2025.114765.
DOI

[reference-28] [28]
S. Xu and K. Xu, Resistance distances in generalized join graphs, Discrete Appl. Math. 362 (2025), 18–33. 10.1016/j.dam.2024.11.013.
DOI