A395521 Number of non-isomorphic abelian groups appearing as the sandpile group K(G) of a connected graph on n vertices.

1, 2, 5, 16, 71, 461, 4855

Offset

2,2

Comments

The sandpile group (also known as critical group, Jacobian, or Picard group) of a connected graph G is K(G) = Z^(n-1) / image(L'), where L' is the reduced Laplacian, the Laplacian of G with one row and column removed; the choice of row and column does not affect the group up to isomorphism. By the matrix-tree theorem, |K(G)| equals the number of spanning trees of G.

This sequence counts the number of distinct (up to abelian group isomorphism) groups arising as K(G) over all connected graphs G on n vertices. The number of connected graphs on n vertices is A001349; many of these share the same sandpile group, so a(n) <= A001349(n).

a(2)-a(8) were computed by exhaustive enumeration of all 12112 connected graphs on n = 2..8 vertices via pynauty, with K(G) determined from the Smith Normal Form of the reduced Laplacian.

References

N. L. Biggs, Chip-firing and the critical group of a graph, J. Algebraic Combin. 9 (1999), 25-45.

D. J. Lorenzini, A finite group attached to the Laplacian of a graph, Discrete Math. 91 (1991), 277-282.

Links

Table of n, a(n) for n=2..8.

M. Baker and S. Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), 766-788.

Example

n=4: of the 6 connected graphs on 4 vertices, the realized sandpile groups are: trivial (the 2 trees), Z/3 (the triangle plus a pendant), Z/4 (the 4-cycle), Z/8 (the 4-cycle plus one chord), and Z/4 x Z/4 (the complete graph K_4). So a(4) = 5.

Crossrefs

Cf. A001349 (connected graphs on n vertices).

Cf. A000055 (trees on n vertices, the case K(G) trivial; counted by this sequence as the value 1).

Cf. A000272 (n^(n-2), the maximum |K(G)| achieved by K_n via Cayley's formula).

Sequence in context: A129092 A110710 A381515 * A245881 A078639 A002632

Adjacent sequences: A395517 A395519 A395520 * A395522 A395523 A395524

Keyword

nonn,more

Author

Alex Towell, Apr 27 2026

Status

approved