THE CRITICAL GROUP OF A THRESHOLD GRAPH

HANS CHRISTIANSON AND VICTOR REINER

Abstract. The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph. The structure of this group is a subtle isomorphism invariant that has received much attention recently, partly due to its relation to the graph Laplacian and chip-firing games. However, the group structure has been determined for relatively few classes of graphs.

We conjecture a relation between the group structure and the Laplacian spectrum for a large class of graphs having integer spectra (the decomposable graphs of Kelmans). Based on computer evidence, we conjecture the exact group structure for the well-studied subclass of threshold graphs, and prove this conjecture for the subclass which we call generic threshold graphs.

1. Introduction and background

Let G = (V, E) be a finite graph without self-loops, but with multiple edges allowed. That is, V is a set, and E is a multiset of pairs {v, v′} ⊂ V with v ≠ v′. The critical group K(G) [7, §14.13] (also called the Picard group and Jacobian group in [2, 4]) is a finitely generated abelian group which is a subtle isomorphism invariant of G. The order of K(G) is the number of spanning forests in G, and it has a close connection with the Laplacian matrix of G, Kirchoff’s matrix-tree theorem, and a chip-firing game on G (also known as abelian sandpiles in the physics literature) -see [2, 4, 5, 7].

There are several equivalent intrinsic definitions of K(G), but for our purposes the most convenient will be the following. Consider the usual |V | × |V | Laplacian matrix L(G) defined by

L(G)_{v,v′} = \begin{cases}deg_{G}(v) & if v = v′ \\ −m_{v,v′′} & else \end{cases}

where m_{v,v′} denotes the multiplicity of the edge {v, v′} in E. It is not hard to see that L(G) has rank |V | − c where G has c connected components – the nullspace of L(G) is spanned by functions on V which are constant on the connected components. Thinking of the Laplacian as representing an abelian group homomorphism L(G) : ℤ^{|V |} → ℤ^{|V |}, the critical group K(G) is the unique finite abelian group such

Key words and phrases. Graph Laplacian, critical group, Picard group, abelian sandpile, chipfiring, Smith normal form, matrix-tree theorem, threshold graph.

This paper arose from work supported by the Summer 2000 and 2001 University of Minnesota Research Experiences for Undergraduates (REU) program, and partly supported by NSF grant DMS–9877047. The authors thank Paul Bendich and Tristram Bogart for proving Theorem 16 and conjecturing Theorem 20 based on extensive computer explorations, and thank Hyung Kim for the crucial computer explorations which led to Conjecture 10. They also thank Dan Drake, and David Treumann for helpful conversations.

that the cokernel can be expressed

ℤ^{|V |}/imL(G) ≅ ℤ^{c} ⊕ K(G).

There are a few results relating the group structure of K(G) to the graphical structure of G [1, 5, 9, 11], or partly determining the group structure for various classes of graphs, such as [5, 6, 11]. There are very few families of graphs for which the group structure has been completely determined:

• complete graphs and complete bipartite graphs [11]

• cycles [13]

• wheels [5] The point of this paper is to look at the structure of K(G) for a class of graphs G

which have integer Laplacian spectra, namely the decomposable graphs introduced by Kelmans. In Section 2, we define these graphs, and point out that their secondlargest to second-smallest eigenvalues

λ_{2} ≥ λ_{3} ≥ ⋯ ≥ λ_{|V |−1}

are non-negative integers which factor |K(G)| (Proposition 3). We then conjecture that these integers may be grouped into products which determine the orders of the cyclic groups in the product structure of K(G) (Conjecture 4). We do not conjecture a general rule on how this grouping occurs for every decomposable graph. However, we do conjecture such a rule for the well-studied subclass of threshold (or 1-decomposable or degree-maximal) graphs (Conjecture 10), based on a convenient description of their Laplacian spectrum observed by Merris [12]. In Section 3 we prove this for what we call generic threshold graphs (Theorem 20).

The method of proof is essentially just a verification that certain integer row and column operations can bring L(G) into the desired diagonal form, and hence not so interesting in itself. Rather our motivation came from the following sources:

• Knowing the structure of K(G) for (generic) threshold graphs G may prove useful in testing conjectures on the relation of K(G) to properties of G for all graphs.

• The phrasings of Conjecture 10 and Theorem 20 demonstrate that K(G) is subtle. In particular, Conjecture 10 shows that the interaction of numbertheoretic properties of the integer eigenvalues can play an important role in the structure of K(G).

• Threshold graphs are conjectured to be extremal from a viewpoint which compares their Laplacian spectra to their degree sequences [8, Conjecture 2]. Perhaps their critical groups K(G) are also extremal from some analogous viewpoint, and our results/conjectures will lead to bounds on K(G) valid for all graphs?

2. Decomposable, threshold graphs- conjectures relating K(G) to the Laplacian spectrum

We begin by recalling a version of the celebrated Kirchoff matrix-tree theorem which relates the eigenvalues of the Laplacian L(G) to the number κ(G) = |K(G)| of spanning trees in G. Our convention for the eigenvalues of L(G) will be to index them in weakly decreasing order:

λ_{1} ≥ ⋯ λ_{n−1} ≥ λ_{n} = 0

where n := |V | is the number of vertices of G.

Note that the number of occurrences of 0 as an eigenvalue is the number c of connected components in G, so λ_{n−1} > 0 if and only if G is connected. In what follows, we will often restrict without loss of generality to the case where G is connected. Theorem 1. (see e.g. [3, Corollary 6.5]) For any graph G, the tree number κ(G) satisfies

κ(G) = \frac{λ_{1} ⋯ λ_{n−1}}{n} . □

There are some natural constructions on graphs which behave well with respect to eigenvalues, and in particular preserve the property of having integer Laplacian eigenvalues. For example, trivially the disjoint union G = G_{1} + G_{2} of two graphs has L(G) = L(G_{1}) ⊕ L(G_{2}) and hence its eigenvalues are the (multiset) union of the eigenvalues for each G_{i}. It is also well-known [7, Lemma 13.1.3] that if G has no multiple edges, then its complement graph \overline{G} (having same vertex set V, and edge set equal to the pairs in V which are not edges of G) satisfies

λ_{i}(\overline{G}) = n − λ_{n−i}(G) for i = 1, 2, …, n − 1.

This motivates the following definition of Kelmans (see [10]). Definition 2. The class of decomposable graphs is the smallest class closed under the operation of taking disjoint unions and complements, and which contains the graph K_{1} consisting of a single vertex and no edges^{1}.

Clearly the Laplacian spectrum of a decomposable graph will be all integers. Proposition 3. For any connected decomposable graph on n vertices, the largest Laplacian eigenvalue λ_{1} equals n.

Consequently, the tree number of a connected decomposable graph factors as

κ(G) = λ_{2} ⋯ λ_{n−1}.

Proof. Since graph complementation is an involutive operation, in building up a connected decomposable graph G as a sequence of iterates of the two operations of disjoint union and complementation, one can assume that the last operation is complementation, and the second-to-last is disjoint union. But the disjoint union will produce a disconnected graph H, which has λ_{n−1}(H) = 0, and then complementation will then produce G = \overline{H} having λ_{1}(G) = n − λ_{n−1}(H) = n − 0 = n. □

The previous proposition, along with the fact that K(G) is a finite abelian group satisfying |K(G)| = κ(G), motivates the following conjecture. Conjecture 4. Let G be a connected decomposable graph with Laplacian eigenvalues

n = λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n−1} > λ_{n} = 0.

Then there exists a partition

{2, 3, …, n − 1} = ⊔_{i=1}^{r}B_{r}

1Although we will not use it here, it can be shown that decomposable graphs are characterized by the property of not containing a path P_{4} with 4 vertices as a vertex-induced subgraph [10, p.

such that

K(G) ≅ ⨁_{i=1}^{r} ℤ/n_{r}ℤ

where n_{r} := ∏_{j∈B_{r}} λ_{j}. Remark 5. One might hope for a similar conjecture in a more general context by adding the Cartesian product operation into the definition of decomposable graphs. Given two graphs G_{1} = (V_{1}, E_{1}), G_{2} = (V_{2}, E_{2}), one can check that their Cartesian product

G_{1} × G_{2} := (V_{1} × V_{2}, (V_{1} × E_{2}) ∪ (E_{1} × V_{2}))

has Laplacian L(G_{1} × G_{2}) acting on ℝ^{V_{1}×V_{2}} ≅ ℝ^{V_{1}} ⊗ ℝ^{V_{2}} in such a way that

L(G_{1} × G_{2}) = L(G_{1}) ⊗ 1 + 1 ⊗ L(G_{2}).

As a consequence, its multiset of eigenvalues is given by all possible sums λ^{(1)} +λ^{(2)} where λ^{(i)} is an eigenvalue of L(G_{i}). Therefore the Cartesian product operation also preserves the property of having integer Laplacian spectrum.

Unfortunately, Proposition 3 fails for the larger class of graphs which is closed under disjoint union, complementation, and Cartesian product. For example, the complement of the Cartesian product K_{3} × K_{2} (where K_{n} is the complete graph without multiple edges on n vertices) has n = 6 vertices, but its Laplacian eigenvalues are (4, 3, 3, 1, 1, 0).

At present we do not know how to write down explicitly the conjectural partition occurring in Conjecture 4 for every decomposable graph. But for the well-studied subclass of threshold graphs, we (conjecturally) do. Definition 6. A graph G is threshold if it can be obtained from K_{1} by iterating the operations of complementation and disjoint union with a new copy of K_{1} in any order^{2}. Such graphs are called 1-decomposable in [10], and degree-maximal in [12].

Equivalently, G is threshold if it can be obtained from K_{1} by iterating the operations of adding in a new vertex which is connected to no other vertex (an isolated vertex) or adding in a new vertex connected to every other vertex (a cone vertex, or universal vertex). We will call the sequence of operations which describes this process the building sequence for G. For example, the graph K_{1} + K_{1} + K_{4} has building sequence (cone, cone, cone, isolated, isolated).

Threshold graphs have many different characterizations, and one of their pleasant features is that they are completely determined up to isomorphism by their vertex degree sequence d = (d_{1} ≥ ⋯ ≥ d_{n}), listed in weakly decreasing order. This means that, in principle, any isomorphism invariant of a threshold graph should be expressible in terms of d, and in Merris [12] gave a very elegant expression for the Laplacian spectrum of this form. Recall the following definition from the theory of integer partitions. Definition 7. The Ferrers diagram for any weakly decreasing sequence of non-negative integers (d_{1} ≥ ⋯ ≥ d_{r}) is a left-justified array of squares in the plane having d_{i} squares in row i for each i.

2As with decomposable graphs, threshold graphs also have a characterization by excluding certain vertex induced subgraphs- they exclude the 4-cycle C_{4}, the path with 4 vertices P_{4}, and the disjoint union K_{2} + K_{2}.

Theorem 8. [12] For any threshold graph G, the eigenvalues λ_{1} ≥ ⋯ ≥ λ_{n} of L(G) are the column lengths c_{1} ≥ ⋯ ≥ c_{n} in the Ferrers diagram for the degree sequence of G. □

Combining this with Proposition 3 gives the following.

Corollary 9. For a connected threshold graph G, in the notation of the previous theorem, one has

|K(G)| = κ(G) = c_{2} … c_{n−1}. □

Motivated by this corollary and extensive computer experimentation during Summer 2000 and 2001 REU projects at the University of Minnesota, we were led to the following precise form of Conjecture 4 for threshold graphs. Let G be a threshold graph, and let c_{2} ≥ … ≥ c_{s} ≥ 2 be the column lengths of size at least 2 in the Ferrers diagram for its degree sequence. Re-order these column lengths as c′_{2}, …, c′_{s} according according to the following rule: List the occurrences of the largest c_{i} first, then the occurrences of the smallest, then the second largest, then the second smallest, etc. Form the graph H having vertex set {2, 3, …, s} and an edge {i, i + 1} whenever c′_{i}, c′_{i+1} are unequal but not relatively prime. Let {2, 3, …, s} = ⊔_{i=1}^{r}B_{i} be the decomposition of the vertex set of H into connected components.

Conjecture 10. If G is a threshold graph, with notation as above, one has

K(G) ≅ ⨁_{i=1}^{r} ℤ/n_{r}ℤ

where n_{r} := ∏_{j∈B_{r}} c′_{j}.

Remark 11. Note that it is reasonable for the statement of the conjecture to ignore columns of length 1 in the Ferrers diagram– removing them corresponds to removing the vertices of degree one in a threshold graph G, and it is easy to see this does not affect the structure of the critical group [13, Proposition 1]. In other words, we are free to restrict attention to threshold graphs which are not only connected, but also 2-(vertex)-connected.

Remark 12. One might ask if Conjecture 10 holds more generally for all decomposable graphs, provided that one replaces the integer c_{i} with the integer eigenvalue λ_{i} throughout the statement. However, this turns out to be incorrect, as shown already for the smallest example of a connected, decomposable, but non-threshold graph: G = K_{2} × K_{2}, which is the complement of the disjoint union K_{2} + K_{2}. This G has Laplacian eigenvalues (4, 2, 2, 0), so that the analogous conjecture would predict K(G) ≅ ℤ/2ℤ ⊕ ℤ/2ℤ, but it turns out that K(G) ≅ ℤ/4ℤ .

Conjecture 10 has been checked via computer for all threshold graphs having up to 40 edges. In the next section we will prove it for the large subclass which we call generic threshold graphs.

Example 13. Let G be a threshold graph built up from K_{1} by adding 8 more cone and isolated vertices in the building sequence:

(isolated, cone, isolated, cone, isolated, isolated, cone, cone).

Numbering the vertices V = {1, …, 9} in weakly decreasing order of degree, then

E = {12, 13, 14, 15, 16, 17, 18, 19,
23, 24, 25, 26, 27, 28, 29,
34, 35, 36, 37,
45, 46}

and the degree sequence is d = (8, 8, 6, 5, 4, 4, 3, 2, 2), whose Ferrers diagram (with row and column lengths labelled) is

9 9 7 6 4 3 2 2
8 × × × × × × × ×
8 × × × × × × × ×
6 × × × × × ×
5 × × × × ×
4 × × × ×
4 × × × ×
3 × × ×
2 × ×
2 × ×

The column lengths in the Ferrers diagram for the degree sequence are

(c_{1}, c_{2}, …, c_{n}) = (9, 9, 7, 6, 4, 3, 2, 2, 0)

which by Theorem 8 coincide with the eigenvalues of L(G). It happens that in this case there are no columns of length 1, so that s = n − 1 = 8, and the re-ordering of the relevant column lengths (c_{2}, …, c_{s}) is (c′_{2}, …, c′_{s}) = (9, 2, 2, 7, 3, 6, 4). Therefore Conjecture 10 predicts

K(G) ≅ ℤ/9ℤ ⊕ ℤ/2ℤ ⊕ ℤ/2ℤ ⊕ ℤ/7ℤ ⊕ ℤ/(3 · 6 · 4)ℤ.

This turns out to be correct, as can be verified for example by a Smith normal form calculation on L(G) in a computer algebra package.

3. Generic threshold graphs

In this section, we define the class of generic threshold graphs, and prove that they satisfy Conjecture 10. As in Remark 11, we may assume whenever convenient that G is 2-connected, so that it has neither isolated vertices nor vertices of degree one. We will also implicitly use repeatedly the fact that the cokernel of an integer matrix is not affected (up to isomorphism) by row and column operations that are invertible over the integers. Definition 14. Consider the equivalence relation on the vertices V of a threshold graph given by having the same degree, and call the equivalence classes blocks. It is easy to see that in a threshold graph, two vertices are in the same block if and only if they are equivalent under a graph automorphism.

Both as a warm-up, and to introduce some key lemmas for later use, we treat separately the cases where the threshold graph G has only one block or two blocks.

3.1. The case of one block. Assuming that G is 2-connected, if G has only one block then it is a complete graph K_{n} for some n ≥ 2. One can then apply the following lemma with d = n − 1, to conclude the well-known fact that

K(K_{n}) ≅ (ℤ/nℤ)^{n−2}.

Lemma 15. The n × n matrix A = (a_{ij}) defined by

a_{ij} = \begin{cases}d & if i = j \\ −1 & else \end{cases}

is equivalent by row and column operations over the integers to a diagonal matrix with entries

1, \underbrace{d + 1, …, d + 1}_{n−2 times}, (d − n + 1)(d + 1).

Proof. Straightforward; we omit the details. □

3.2. The case of two blocks. Again assuming that G is 2-connected, if G has two blocks then it is the join of a complete graph K_{k} with i isolated vertices, for some k, i ≥ 2. In other words, k of the vertices are cone vertices connected to all others, and i of the vertices are connected only to these k cone vertices. Note that the total number of vertices is n = k+i. One can then apply Lemma 18 below, with α = n − 1, β = k and A′ the empty matrix to immediately deduce the following.

Theorem 16. For a 2-connected threshold graph G having two blocks, with notation as above,

K(G) ≅ (ℤ/nℤ)^{k−2} ⊕ (ℤ/kℤ)^{i−2} ⊕ ℤ/knℤ. □

Remark 17. Using the fact that

(1)  ℤ/mnℤ ≅ ℤ/mℤ × ℤ/nℤ when gcd(m, n) = 1,

one can check that Theorem 16 agrees with Conjecture 10 in the case of two blocks.

The key lemma in both the two block case and in the generic case is the following calculation.

Lemma 18. Assume that the integer matrix A shown in Figure 1 has all row and column sums equal to λ. Then A is equivalent by row and column operations over the integers to the matrix shown in Figure 2, with

\begin{aligned}δ & = λ(α + 1) \\ γ & = β(α + 1). \end{aligned}

Proof. Specifically, P_{1}AP_{2} has the form in Figure 2, where P_{1}, P_{2} are the integer matrices shown in Figures 3, 4 respectively. We omit the tedious but straightforward verification that det(P_{i}) = ±1 for i = 1, 2, and that P_{1}AP_{2} has the asserted form.

□

8 HANS CHRISTIANSON AND VICTOR REINER

Figure 1. The matrix A.

Figure 2. A matrix which is equivalent to A by integer row and column operations.

CRITICAL GROUP OF A THRESHOLD GRAPH 9

Figure 3. The matrix P_{1}.

Figure 4. The matrix P_{2}. Here ∗ = −2 − λ and ∗∗ = 1 + λ.

3.3. The generic case. For the remainder, G is a threshold graph with c_{2} ≥ … ≥ c_{s} ≥ 2 the column lengths of size at least 2 in the Ferrers diagram for its degree sequence, and (c′_{2}, …, c′_{s}) is the re-ordering as Section 2. As in the previous section, we are free to assume that G is 2-connected whenever convenient.

Definition 19. Say that G is a generic threshold graph if for each i in the range 3, 4, …, s−1 there are at least two occurrences of c′_{i} among the column lengths c_{i} (or equivalently, among (c_{2}, …, c_{s}), or among (c′_{2}, …, c′_{s})).

For 2-connected threshold graphs, this definition has a convenient rephrasing in terms of the building sequence: G is generic threshold if and only if one encounters neither of the following subsequences in its building sequence:

..., cone, isolated, cone, ... ..., isolated, cone, isolated, ...

When G is generic threshold, we will prove an equivalent phrasing of Conjecture 10 (the equivalence again uses the fact (1)). Form the graph H′ on vertex set {2, 3, …, s} having an edge {i, i + 1} whenever c′_{i}, c′_{i+1} are unequal (but possibly relatively prime). Let {2, 3, …, s} = ⊔_{i=1}^{r}B_{i} be the decomposition of the vertex set of H′ into connected components. Note that the genericity assumption implies that this new graph H′ will have no connected components with more than one edge.

Theorem 20. Let G be a generic threshold graph, with notation as above. Then

K(G) ≅ ⨁_{i=1}^{r} ℤ/n_{r}ℤ

where n_{r} := ∏_{j∈B_{r}} c′_{j}.

Proof. Order the vertices of G by degree, and index the rows and columns of L(G) in this order. Assume that the number of blocks of vertices in G is either 2m or 2m+1, depending on its parity. One can then perform m stages of row and column operations by applying Lemma 18 each time. At the i^{th} stage, one applies the lemma with α, β, λ equal to the i^{th} largest, i^{th} smallest, (i − 1)^{st} smallest values occurring among the set of vertex degrees of G, respectively (and by convention, at the first stage one takes λ = 0).

After performing these equivalences, if G has 2m blocks then one need perform no more row and column operations, i.e. the resulting matrix is in diagonal form. If there are 2m + 1 blocks, one must apply Lemma 15 once with n, d chosen as follows. Consider the block of vertices which are all connected to each other (i.e. they induce a subgraph which is complete) and which have minimum degree among all such blocks. Then apply Lemma 15, choosing n to be the cardinality of this block, and d the common vertex degree of all vertices in this block.

In either case (2m or 2m + 1 blocks) one can check that the resulting diagonal matrix has entries as predicted by the theorem; we omit this bookkeeping, but illustrate the proof with an example below. □

Example 21. We illustrate the proof of Theorem 20 for the (unique) threshold graph on 15 vertices having degree sequence d = (14, 14, 14, 11, 11, 11, 8, 8, 8, 6, 6, 6, 3, 3, 3).

Note that there are 5 vertex blocks, each of size 3. Since the vertex blocks are all of size at least 2, it is a generic threshold graph. Since the number of blocks is 5 = 2m + 1 for m = 2, we will be applying Lemma 18 twice, and then Lemma 15 once.

Indexing the rows and columns in weakly decreasing order of vertex degree, the Laplacian L(G) is

[\begin{matrix}14 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 \\ −1 & 14 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 \\ −1 & −1 & 14 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 \\ −1 & −1 & −1 & 11 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & 11 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & −1 & 11 & −1 & −1 & −1 & −1 & −1 & −1 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & −1 & −1 & 8 & −1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & −1 & −1 & −1 & 8 & −1 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & 8 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & −1 & −1 & 0 & 0 & 0 & 6 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & −1 & −1 & 0 & 0 & 0 & 0 & 6 & 0 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & −1 & −1 & 0 & 0 & 0 & 0 & 0 & 6 & 0 & 0 & 0 \\ −1 & −1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 \\ −1 & −1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 \\ −1 & −1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \end{matrix}] .

After applying Lemma 18 once with α, β, λ equal to 14, 3, 0, one obtains the block diagonal matrix

[\begin{matrix}1 \\ & 1 \\ & & 15 \\ & & & A′ \\ & & & & 3 \\ & & & & & 0 \\ & & & & & & 3 · 15 \end{matrix}]

where

A′ = [\begin{matrix}11 & −1 & −1 & −1 & −1 & −1 & −1 & −1 & −1 \\ −1 & 11 & −1 & −1 & −1 & −1 & −1 & −1 & −1 \\ −1 & −1 & 11 & −1 & −1 & −1 & −1 & −1 & −1 \\ −1 & −1 & −1 & 8 & −1 & −1 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & 8 & −1 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & −1 & 8 & 0 & 0 & 0 \\ −1 & −1 & −1 & 0 & 0 & 0 & 6 & 0 & 0 \\ −1 & −1 & −1 & 0 & 0 & 0 & 0 & 6 & 0 \\ −1 & −1 & −1 & 0 & 0 & 0 & 0 & 0 & 6 \end{matrix}] .

After applying Lemma 18 to A′ with α, β, λ equal to 11, 6, 3, one obtains the block diagonal matrix

[\begin{matrix}1 \\ & 1 \\ & & 12 \\ & & & A′′ \\ & & & & 6 \\ & & & & & 3 · 12 \\ & & & & & & 6 · 12 \end{matrix}] where A′′ = [\begin{matrix}8 & −1 & −1 \\ −1 & 8 & −1 \\ −1 & −1 & 8 \end{matrix}] .

Lastly, applying Lemma 15 to A′′ with n = 3, d = 8, one obtains the diagonal matrix

[\begin{matrix}1 & 0 & 0 \\ 0 & 9 & 0 \\ 0 & 0 & 6 · 9 \end{matrix}] .

This implies that

\begin{matrix}K(G) ≅ & ℤ/15ℤ ⊕ ℤ/3ℤ ⊕ ℤ/3 · 15ℤ \\ ⊕ & ℤ/12ℤ ⊕ ℤ/6ℤ ⊕ ℤ/3 · 12ℤ \\ ⊕ & ℤ/6 · 12ℤ ⊕ ℤ/9ℤ ⊕ ℤ/6 · 9ℤ. \end{matrix}

We check that this agrees with the prediction of Conjecture 10 or Theorem 20 (it happens that in this example, the graphs H, H′ will coincide). The non-zero column lengths in the Ferrers diagram for the degree sequence of G are

(15, 15, 15, 12, 12, 12, 9, 9, 6, 6, 6, 3, 3, 3).

This implies that the re-ordered column lengths are

(c′_{2}, c′_{3}, …, c_{14}) = (15, \underbrace{15, 3}, 3, \underbrace{3, 12}, 12, \underbrace{12, 6}, 6, \underbrace{6, 9}, 9),

in which the column lengths which will be connected by an edge in the graph H′ are shown bracketed together. Note that the unbracketed column lengths along with the products of two bracketed column lengths account for the ℤ/nℤ factors in our expression for K(G), as predicted by the theorem.

References

[1] K.A. Berman, Bicycles and spanning trees. SIAM J. Algebraic Discrete Methods 7 (1986), 1–12.

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

[3] N.L. Biggs, Algebraic graph theory, second edition. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1993.

[4] N.L. Biggs, Algebraic potential theory on graphs. Bull. London Math. Soc. 29 (1997), 641–682.

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

[6] D. Dhar, P. Ruelle, S. Sen, D.-N. Verma, Algebraic aspects of abelian sandpile models. J. Phys. A 28 (1995), 805–831.

[7] C. Godsil, G. Royle, Algebraic graph theory. Graduate Texts in Mathematics 207. Springer-Verlag, New York, 2001.

[8] R. Grone, R. Merris, The Laplacian spectrum of a graph. II. SIAM J. Discrete Math. 7 (1994), 221–229.

[9] R. Grone, R. Merris, W. Watkins, Laplacian unimodular equivalence of graphs. Combinatorial and graph-theoretical problems in linear algebra (Minneapolis, MN, 1991), 175–180, IMA Vol. Math. Appl. 50, Springer, New York, 1993.

[10] P.L. Hammer, A.K. Kelmans, Laplacian spectra and spanning trees of threshold graphs. First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz). Discrete Appl. Math. 65 (1996), 255–273.

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

[12] R. Merris, Degree maximal graphs are Laplacian integral. Linear Algebra Appl. 199 (1994), 381–389.

[13] R. Merris, Unimodular equivalence of graphs. Linear Algebra Appl. 173 (1992), 181–189.

   E-mail address: hans@friedchicken.org

School of Mathematics, University of Minnesota, Minneapolis MN 55455

   E-mail address: reiner@math.umn.edu