A395521 - OEIS

%I #8 May 01 2026 18:46:20

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

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

%C 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.

%C 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).

%C 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.

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

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

%H M. Baker and S. Norine, <a href="https://doi.org/10.1016/j.aim.2007.04.012">Riemann-Roch and Abel-Jacobi theory on a finite graph</a>, Adv. Math. 215 (2007), 766-788.

%e 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.

%Y Cf. A001349 (connected graphs on n vertices).

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

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

%K nonn,more

%O 2,2

%A _Alex Towell_, Apr 27 2026