# Chip-firing and critical groups of signed graphs

Matthew Cho  Massachusetts Institute of Technology<EMAIL_ADDRESS>,  Anton
Dochtermann  Texas State University<EMAIL_ADDRESS>,  Ryota
Inagaki  University of California, Berkeley<EMAIL_ADDRESS>,  Suho
Oh  Texas State University<EMAIL_ADDRESS>,  Dylan Snustad  University of
Minnesota, Twin Cities<EMAIL_ADDRESS>and  Bailee Zacovic  University of
Notre Dame<EMAIL_ADDRESS>
(Date: August 28, 2024)

###### Abstract.

A signed graph $G_{\phi}$ consists of a graph $G$ along with a function $\phi$
that assigns a positive or negative weight to each edge. The reduced signed
Laplacian matrix $L_{G_{\phi}}$ gives rise to a natural notion of chip-firing
on $G_{\phi}$, as well as a critical group ${\mathcal{K}}(G_{\phi})$. Here a
negative edge designates an adversarial relationship, so that firing a vertex
incident to such an edge leads to a loss of chips at both endpoints. We study
chip-firing on signed graphs, employing the theory of chip-firing on
invertible matrices introduced by Guzmán and Klivans. This gives rise to
notions of critical as well as $z$-superstable configurations, both of which
are counted by the determinant of $L_{G_{\phi}}$. We establish general results
regarding these configurations, focusing on efficient methods of verifying the
underlying properties. We then study the critical group of signed graphs in
the context of vertex switching and Smith normal forms. We use this to compute
the critical groups for various classes of signed graphs including signed
cycles, wheels, complete graphs, and fans. In the process we generalize a
number of results from the literature.

2020 _Mathematics Subject Classification_. 05C50, 20K01, 05C22, 91A46

_Key words and phrases_. Signed graphs, chip-firing, critical group

##  1\. Introduction

Chip-firing is a single player game played on a connected graph $G$, where
‘chips’ are placed on the vertices of $G$ and distributed to their neighbors
via simple ‘firing’ moves. The resulting discrete dynamical system has
connections to many areas of algebra, combinatorics, and physics, and has
recently found applications in divisor theory in algebraic geometry. We refer
to the recent texts [9, 15] for an overview of the subject.

In the version of chip-firing most relevant to us, a single vertex of $G$ is
distinguished as the _sink_ , and a number of chips are placed on each nonsink
vertex. This distribution of chips is represented by an integer vector
$\vec{c}\in\mathbb{Z}^{n}$ called a (chip) configuration. If a non-sink vertex
has at least as many chips as its degree, it can fire, passing one chip to
each of its neighbors. If no non-sink vertex can fire we say that the
configuration is $\vec{c}$ is _stable_. At this point the sink can fire,
distributing a chip to each of its neighbors. If $G$ is a connected graph then
any initial configuration eventually stabilizes, as chips are eventually
passed to the sink vertex.

If we use $v_{1},...,v_{n}$ to label the nonsink vertices of $G$, we can
describe the rules of chip-firing via the $n\times n$ reduced Laplacian matrix
$L_{G}$. The result of firing a vertex $v_{i}$ on a chip configuration
$\vec{c}$ is then encoded by $\vec{c}-L\vec{e_{i}}$, where $\vec{e_{i}}$ is
$i$th standard basis vector. The matrix $L_{G}$ defines an equivalence
relation on the set of vectors in ${\mathbb{Z}}^{n}$, where $\vec{c}$ and
$\vec{d}$ are _firing equivalent_ if $\vec{c}-\vec{d}$ is contained in the
image of $L_{G}$. This defines the _critical group_ of $G$, given by
$\mathcal{K}(G):={\mathbb{Z}}^{n}/\operatorname{im}L_{G}$.

A configuration $\vec{c}$ is _valid_ (or _effective_) if we have $c_{i}\geq 0$
for all $i=1,\dots,n$. One is interested in finding distinguished valid
configurations in each equivalence class $[\vec{c}]\in{\mathcal{K}}(G)$
defined by $L_{G}$. On the one hand, it can be shown that each $[\vec{c}]$
contains a unique valid configuration that is stable and _critical_ , meaning
that it can be reached from a ‘sufficiently large’ configuration $\vec{b}$ (in
particular $\vec{b}$ should have the property that any vertex can fire). The
critical configurations of a graph $G$ can also be used to understand
$\mathcal{K}(G)$, as one can show that the stablization of the sum of two
critical configurations is critical.

On the other hand, one can show that each $[\vec{c}]$ contains a unique valid
configuration that is _superstable_ , meaning that it is stable under _set-
firings_. A superstable configuration is also the solution of a certain energy
minimization problem, and the set of superstable configurations can be seen to
coincide with the set of _$G$ -parking functions_. For a connected graph $G$
there exists a simple bijection between the set of critical configurations and
the set of superstable configurations, both of which are in bijection with the
set of spanning trees of $G$.

In recent years, chip-firing has been extended to more general settings, where
the reduced Laplacian is replaced by other square matrices $M$ with positive
entries on the diagonal and nonnegative entries off the diagonal [12, 13]. One
uses $M$ to define a firing rule that mimics the graphical setting: firing a
‘site’ $v_{i}$ now takes a configuration $\vec{c}$ to $\vec{c}-M\vec{e_{i}}$.
For a well-defined notion of chip-firing we require that $M$ satisfies an
_avalanche finite_ property, so that repeated firings of any initial
configuration eventually stabilize in the appropriate sense. The class of
matrices with this property are known as _$M$ -matrices_, and can be
characterized in a number of ways (see below). In [13] Guzmán and Klivans have
shown that the chip-firing theory defined by an $M$-matrix leads to good
notions of critical and superstable configurations. An important subtlety here
is that one must consider _multiset_ firings and the notion of
‘$z$-superstability’, we review these concepts below.

###  1.1. Our contributions.

In this paper we study chip-firing on a _signed graph_ $G_{\phi}$, where each
edge of a graph $G$ is assigned a positive or negative weight according to a
function $\phi$. Now when a vertex fires, if one of its incident edges is
negative, both that vertex and its neighbor lose a chip. Such a setup can be
thought of as modeling a process where both antagonistic (negative) and
cooperative (positive) relations exist. A signed graph $G_{\phi}$ comes with a
(reduced) signed Laplacian matrix $L_{G_{\phi}}$ which, as above, defines a
chip-firing rule and also a critical group ${\mathcal{K}}(G_{\phi})$. For
signed graphs, the cardinality of ${\mathcal{K}}(G_{\phi})$ can be understood
in terms of combinatorial objects that generalize spanning trees.

The matrix $L_{G_{\phi}}$ is not necessarily an $M$-matrix (for example it can
have positive entries off the diagonal), and hence does not come with a pre-
existing notion of chip-firing that relates to its critical group (as far as
we know). However, signed graphs provide a natural setting to employ a theory
of chip-firing on invertible matrices developed by Guzmán and Klivans in [14].
In this setup, the chip-firing theory is governed by a pair $(L,M)$ of
$n\times n$ matrices, where $L$ is invertible and $M$ is an $M$-matrix.

For a signed graph $G_{\phi}$ we let $G$ denote the underlying (unsigned)
graph. We take $L=L_{G_{\phi}}$ to be the reduced signed Laplacian, and choose
$M=L_{G}$ to be the reduced Laplacian of $G$. Results of [14] tell us that the
pair $(L,M)$ gives rise to notions of critical and $z$-superstable
configurations, unique to each equivalence class determined by $L$ (see
Definitions 2.16 and 2.14). This approach to chip-firing on signed graphs was
used by Moore in his thesis [19].

$q$$+$$+$$+$$+$$+$$q$$+$$+$$+$$-$$+$$|G|$$G_{\phi}$$L_{|G|}=\begin{pmatrix}2&-1&0\\\
-1&3&-1\\\
0&-1&2\end{pmatrix}$$L_{G_{\phi}}=\begin{pmatrix}2&{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}+1}&0\\\
{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}+1}&3&-1\\\
0&-1&2\end{pmatrix}$$v_{1}$$v_{1}$$v_{2}$$v_{2}$$v_{3}$$v_{3}$ Figure 1. A
signed graph $G_{\phi}$ and its underlying graph $G=|G|$.

In the theory of chip-firing on the pair $(L,M)$, the class of _valid_
configurations are no longer simply vectors with nonnegative entries, but
rather integer points in the rational cone determined by $LM^{-1}$ (see
Definition 2.12). Our first result says that for the case of signed graphs,
these points will always have nonnegative entries.

######  Proposition 3.1.

For any signed graph $G_{\phi}$, the set of valid configurations determined by
the chip-firing pair $(L,M)$ is contained in the nonnegative orthant.

We next investigate the critical configurations of signed graphs. In classical
chip-firing, one has a number of results to efficiently detect whether a
configuration is critical. For example, [15, Theorem 2.6.3] says that a valid
configuration $\vec{c}$ is critical if and only if the stabilization after
firing the sink recovers $\vec{c}$. Furthermore, for a graph $G$, the ‘maximal
critical’ configuration $\vec{c}_{\text{max}}$ defined by
$(\vec{c}_{\text{max}})_{i}=\deg(v_{i})-1$ provides a bijection between the
critical and superstable configurations. In particular $\vec{c}_{\text{max}}$
is a valid critical configuration such that $\vec{c}\leq\vec{c}_{\text{max}}$
(componentwise) for any stable configuration $\vec{c}$. As shown in [13] these
correspondences extend to the setting of chip-firing on $M$-matrices.

Here we seek to extend these notions to the setting of signed graphs. For a
signed graph $G_{\phi}$ with sink vertex $q$ and nonsink vertices
$v_{1},\dots,v_{n}$ we define the configuration $\vec{s}\in\mathbb{Z}^{n}$ as

$(\vec{s})_{i}:=\begin{cases}1,&\mbox{$v_{i}$ is adjacent to $q$}\\\
0,&\mbox{otherwise}.\end{cases}$

Note that adding the vector $\vec{s}$ to any configuration $\vec{c}$ is the
analogue of ‘firing the sink’. We then have the following method of finding
critical configurations for signed graphs.

######  Theorem 3.3.

Let $G_{\phi}$ be a signed graph with sink $q$. Suppose $\vec{s}$ is a valid
configuration and pick a positive integer $N_{0}$ such that
$L^{-1}(N_{0}\vec{s})\in\mathbb{Z}_{\geq 0}$. Then a configuration $\vec{c}\in
S^{+}$ is critical if and only if
$\mbox{stab}_{S^{+}}(\vec{c}+N_{0}\vec{s})=\vec{c}$.

For an unsigned graph $G$, firing the sink always leads to a valid (i.e.
nonnegative) configuration. For the case of a signed graph $G_{\phi}$ it is in
general difficult to decide whether $\vec{s}$ is valid (see the examples in
Section 2.5). However, if $G_{\phi}$ has a _universal sink_ $q$ and is
_signed-regular_ (the number of negative and positive edges incident to $v$ is
the same for all nonsink vertices $v$) then one can guarantee this property.
See Corollary 3.4.

For the case of certain signed-regular graphs, we also have a notion of a
‘maximal critical configuration’, analogous to the configuration
$\vec{c}_{max}$ discussed above. In what follows we let $-G$ denote the signed
graph where all edges not incident to the sink have a negative sign.

######  Proposition 3.5.

Let $G_{\phi}$ be a signed-regular graph with universal sink. Suppose each
nonsink vertex is incident to $m$ edges, with $m_{-}$ of them negative, and
let $m^{\prime}=(m(2m_{-}+1)-1)$. Then $m^{\prime}\vec{1}$ is a critical
configuration. Furthermore if $G_{\phi}=-G$, then any stable configuration
$\vec{c}$ satisfies $\vec{c}\leq m^{\prime}\vec{1}$.

Examples of negative graphs include the negative complete graphs $-K_{n}$ and
the negative wheels $-W_{n}$, as discussed in Sections 5 and 6.

We next turn to the set of $z$-superstable configurations of a signed graph
$G_{\phi}$. By definition, to determine whether a valid configuration is
$z$-superstable one must check firings of all nonempty multisets of vertices,
and hence a priori we have no algorithm to check for this property. However,
we show that for the case of signed graphs, simple set (as opposed to
multiset) firings suffice to check for $z$-superstability.

######  Theorem 3.6.

Suppose $G_{\phi}$ is a signed graph with sink $q$. Then a valid configuration
$\vec{c}\in S^{+}$ is $z$-superstable if and only if
$ML^{-1}\vec{c}-M\vec{z}\not\geq\vec{0}$ for any nonzero vector in
$\\{0,1\\}^{n}$.

In the language of chip-firing, Theorem 3.6 says that a configuration is
$z$-superstable if and only if it is _$\chi$ -superstable_. In addition, we
can use the superstable configurations of the underlying graph $G$ to generate
certain $z$-superstable configurations of $G_{\phi}$.

######  Proposition 3.8.

Let $G_{\phi}$ be a signed graph with sink $q$, and let $G$ denote its
underlying graph. Suppose $\vec{v}\in\frac{1}{\det L}{\mathbb{Z}}^{n}$ is a
vector such that $\vec{v}\leq\vec{w}$ for some superstable configuration
$\vec{w}$ of $G$. Then if $\vec{c}=LM^{-1}\vec{v}$ is valid we have that
$\vec{c}$ is $z$-superstable.

####  1.1.1. Critical groups of signed graphs

As discussed above, if $G_{\phi}$ is a signed graph its reduced Laplacian
$L=L_{G_{\phi}}$ defines the critical group
${\mathcal{K}}(G_{\phi}):={\mathbb{Z}}^{n}/L$. Here we study the properties of
this group, and for instance obtain the following way to compute the identity
element.

######  Theorem 3.9.

Suppose $G_{\phi}$ is a signed graph with underlying graph $G$, and let
$\vec{e}_{G}$ denote the identity of the critical group ${\mathcal{K}}(G)$.
Then the identity of ${\mathcal{K}}(G_{\phi})$ is given by

$\vec{e}_{G_{\phi}}=LM^{-1}\vec{e}_{G}.$

If $v$ is a vertex of a signed graph $G_{\phi}$, one can obtain a new signed
graph $G_{\psi}$ by reversing the sign of all edges incident to $v$. This
_vertex switching_ plays an important role in the theory of signed graphs, and
for instance preserves the underlying matroid [25]. To calculate critical
groups of signed graphs, we will make use of the fact that vertex switching
also preserves critical groups.

######  Lemma 3.10.

Suppose $G_{\phi}$ and $G_{\psi}$ are signed graphs that are switching
equivalent. Then we have an isomorphism of critical groups

${\mathcal{K}}(G_{\phi})\cong{\mathcal{K}}(G_{\psi}).$

In the last part of the paper we calculate the critical groups for several
classes of signed graphs, see Figure 2 for an illustration. From Lemma 3.10 we
see that if $G_{\phi}$ is a connected signed graph with sink $q$ such that
$G\backslash q$ is a tree, then there exists an isomorphism of critical groups

${\mathcal{K}}(G_{\phi})\cong{\mathcal{K}}(|G|).$

Using this we show that for any signed cycle $(C_{n})_{\phi}$, we have
$\mathcal{K}((C_{n})_{\phi})\cong\mathbb{Z}_{n}$, see Proposition 4.1. We also
observe a duality between the $z$-superstable and critical configurations for
certain signed cycles. Recall that $-C_{n}$ denotes the _negative cycle_ , a
signed $n$-cycle with all edges not incident to the sink assigned a negative
value.

######  Theorem 4.4.

Suppose $m\geq 2$ is an integer. Then the set map

$\Delta:\\{\mbox{z-superstable configurations of
$-C_{2m+1}$}\\}\to\\{\mbox{critical configurations of $-C_{2m+1}$}\\}$

given by $\vec{c}\mapsto\vec{e}_{-C_{2m+1}}+\vec{c}$ is a bijection.

We next consider complete graphs. For the unsigned case, an extension of
Cayley’s Theorem [15, Theorem 4.5.7] gives
${\mathcal{K}}(K_{n})\cong\mathbb{Z}_{n}^{n-2}$. Understanding critical groups
of arbitrary _signed_ complete graphs seems difficult in general, although we
are able to compute them for a certain class.

######  Proposition 5.1.

Suppose $n\geq 2$ and let $(K_{n})_{\phi}$ be a signed complete graph that is
switching equivalent to $-K_{n}$. Then

${\mathcal{K}}((K_{n})_{\phi})\cong\mathbb{Z}_{n-2}^{n-3}\oplus\mathbb{Z}_{(n-2)(2n-3)}.$

We next consider signed wheels. Here we can completely describe the possible
critical groups, providing a generalization of results of Biggs [5]. In what
follows, we let $f_{n}$ and $\ell_{n}$ denote the $n$th Fibonacci and $n$th
Lucas numbers, respectively.

######  Theorem 6.9.

For any signed wheel $(W_{n})_{\phi}$ with $n\geq 3$ we have:

$\mathcal{K}((W_{n})_{\phi})=\begin{cases}\mathbb{Z}_{f_{n}}\oplus\mathbb{Z}_{5f_{n}},&\mbox{$n$
is odd and $(W_{n})_{\phi}$ is unbalanced}\\\
\mathbb{Z}_{\ell_{n}}\oplus\mathbb{Z}_{\ell_{n}},&\mbox{$n$ is even and
$(W_{n})_{\phi}$ is unbalanced}\\\
\mathbb{Z}_{\ell_{n}}\oplus\mathbb{Z}_{\ell_{n}},&\mbox{$n$ is odd and
$(W_{n})_{\phi}$ is balanced}\\\
\mathbb{Z}_{f_{n}}\oplus\mathbb{Z}_{5f_{n}},&\mbox{$n$ is even and
$(W_{n})_{\phi}$ is balanced}\end{cases}$

and this gives all possible critical groups of $(W_{n})_{\phi}$.

Finally, we compute the critical groups of signed fans, again obtaining a
complete answer.

######  Theorem 7.3.

Let $(F_{n})_{\phi}$ be any signed fan graph where $n\geq 1$. Then
$\mathcal{K}((F_{n})_{\phi})\cong\mathbb{Z}_{f_{2n}}$.

$q$$q$$q$ Figure 2. The Cycle $C_{6},$ the Wheel $F_{6},$ and the Fan $F_{6}$.

The rest of the paper is organized as follows. In Section 2, we review the
basics of signed graph theory and also summarize the Guzmán-Klivans theory of
chip-firing on invertible matrices. Here we also describe the setup for our
study of chip-firing on singed graphs, and provide examples in Section 2.5. In
Section 3, we provide proofs of our main stability results, including Theorem
3.3, Corollary 3.4, Proposition 3.5, and Proposition 3.8. In Section 3.3 we
consider critical groups of signed graphs, and provide proofs of Theorem 3.9.
In Sections 4, 5, 6, and 7, we prove Propositions 4.1 and 5.1, Theorems 6.9
and 7.3, establishing the critical group structures of signed cycles, wheels,
complete graphs, and fans. In Section 8, we discuss some open questions and
potential avenues for future work.

##  2\. Preliminaries

In this section we recall some basic notions from the theory of signed graphs.
We also review the theory of chip-firing on invertible matrices that we employ
in our study.

###  2.1. Signed graphs

The systematic study of signed graphs was initiated by Zaslavsky in [25]. We
recall some basics from the theory, and refer to [25] for details. By a
_simple graph_ we mean a graph with no loops or multiple edges.

######  Definition 2.1.

A signed graph $G_{\phi}$ consists of a simple graph $G=(V,E)$ equipped with a
sign function $\phi:E\rightarrow\\{+,-\\}$. We let $|G|$ denote the signed
graph with all positive edges.

Suppose $G_{\phi}$ is a signed graph with vertex set
$V=\\{v_{1},\dots,v_{n},v_{n+1}\\}$. The _Laplacian_
$\tilde{L}=\tilde{L}_{G_{\phi}}$ is the $(n+1)\times(n+1)$ matrix given by

$(\tilde{L})_{i,j}=\begin{cases}\deg(v_{i}),&\text{ if $i=j$}\\\ -1,&\text{ if
$\\{v_{i},v_{j}\\}\in E$ and $\phi(\\{v_{i},v_{j}\\})=1$}\\\ 1,&\text{ if
$\\{v_{i},v_{j}\\}\in E$ and $\phi(\\{v_{i},v_{j}\\})=-1$}\end{cases}$

for $i,j=1,2,...,n+1$.

The matrix $\tilde{L}$ can also be obtained as $\tilde{L}=\delta\delta^{T}$,
where $\delta$ is the _signed incidence matrix_ associated to $G_{\phi}$. The
_reduced Laplacian_ $L=L_{G_{\phi}}$ is the $n\times n$ matrix obtained by
removing the row and column corresponding to $q=v_{n+1}$. This convention
conflicts with other notations from the literature; here we use $L$ to denote
the reduced Laplacian since it will be our main object of study.

An important construction in the study of signed graphs is the notion of
vertex switching.

######  Definition 2.2.

Suppose $G_{\phi}$ is a signed graph, and let $v\in V$ be a vertex. Define a
new function $\psi:E\rightarrow\\{+,-\\}$ by reversing the sign of every edge
incident to $v$, the resulting signed graph $G_{\psi}$ is said to be obtained
by _switching_ the vertex $v$. A pair of signed graphs $G_{\phi}$ and
$G_{\phi^{\prime}}$ (with the same underlying unsigned graph) are _switching
equivalent_ if there exists a sequence of vertex switchings on $G_{\phi}$ that
results in $G_{\phi^{\prime}}$.

Switching equivalence defines an equivalence relation on all signed graphs on
a fixed underlying graph $G$. From [25, Lemma 3.1] we have the following.

######  Lemma 2.3.

Suppose $G$ is a connected graph and let $T$ be a spanning tree. Each
switching equivalence class of signed graphs on $G$ has a unique
representative which is positive on $T$. In particular, the number of
switching equivalence classes on $G$ is given by $2^{|E|-|V|+1}$.

######  Definition 2.4.

A signed graph $G_{\phi}$ is _balanced_ if it is switching equivalent to the
all-positive graph $|G|$.

The well-known Kirchoff’s Matrix-Tree Theorem says that the determinant of the
reduced Laplacian matrix of a connected graph $G$ is given by the number of
spanning trees of $G$ (see for instance [15] for connections to chip-firing).
This has been generalized to the signed graph setting by Zaslavsky as follows.

######  Theorem 2.5.

[25, Theorem 8A.4] Suppose $G_{\phi}$ is a connected signed graph. Then the
determinant of its (non-reduced) Laplacian $\tilde{L}$ is given by

$\det(\tilde{L})=\sum_{\ell=0}^{n}4^{\ell}b_{\ell},$

where $b_{\ell}$ is the number of independent sets of edges that have $\ell$
cycles.

Here a set of edges is _independent_ if it forms an independent set in the
underlying matroid defined by the signed incidence matrix of $G_{\phi}$, see
[25] for details. This theorem has been further generalized by Chaiken [7],
where one considers the determinant of the matrix obtained by removing a
certain set of rows and columns from $\tilde{L}$. We note that $L$ is the
special case of removing the row and column corresponding to the sink $q$.

In our work, we will often consider signed graphs where every edge not
incident to the sink is negative (and where edges incident to the sink have
arbitrary sign function). We say that $G_{\phi}$ is _negative_ , and write
$G_{\phi}=-G$, if all edges not incident to the sink have a negative sign.
Note that in this case all entries of the reduced Laplacian $L=L_{G_{\phi}}$
are positive. This matrix is often referred to as a _signless Laplacian_ [2]
in the literature.

In the case of negative signed graphs with a sink, Theorem 2.5 can be
rephrased in simpler terms (see Remarks after [25, Theorem 8A.4] or [2,
Theorem 7.8]). In what follows a _$TU$ -subgraph_ is a subgraph of $G$ whose
components are trees or unicylic subgraphs containing a single odd cycle.

######  Theorem 2.6.

Suppose $G_{\phi}$ is a negative signed graph with sink $q$, and let
$L=L_{G_{\phi}}$ denote its reduced Laplacian. Then the determinant of $L$ is
given by

$\det(L)=\sum_{H}4^{c(H)},$

where the sum runs over all spanning $TU$-subgraphs $H$ of $G$ with $c(H)$
unicyclic components, and one tree component that contains the sink $q$.

###  2.2. Chip-firing and critical groups of signed graphs

Now suppose $G_{\phi}$ is a signed graph with sink $q$ and nonsink vertices
$v_{1},\dots,v_{n}$. The reduced signed Laplacian $L=L_{G_{\phi}}$ naturally
defines a chip-firing rule as discussed above: given an integer configuration
$\vec{c}\in{\mathbb{Z}}^{n}$, firing the vertex $i$ leads to the configuration

$\vec{c}^{\prime}=\vec{c}-L\vec{e}_{i},$

obtained by subtracting the $i$th column of $L$. Hence the vertex $v_{i}$
loses $\deg(i)$ number of chips, passing a chip to each adjacent vertex which
shares a positive edge, and deleting a chip at each adjacent vertex which
shares a negative edge.

Fire!$q$$q$$\boldsymbol{-}$$\boldsymbol{+}$$\boldsymbol{+}$$\boldsymbol{+}$$\boldsymbol{+}$$\boldsymbol{+}$$\Longrightarrow$$\underbrace{\begin{pmatrix}0\\\
4\\\ 6\end{pmatrix}}_{\vec{c}}-\underbrace{\begin{pmatrix}3&-1&-1\\\
-1&3&{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}+1}\\\
-1&{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}+1}&3\end{pmatrix}}_{L_{G_{\phi}}}\underbrace{\begin{pmatrix}0\\\
0\\\ 1\end{pmatrix}}_{e_{3}}=\underbrace{\begin{pmatrix}1\\\ 3\\\
3\end{pmatrix}}_{\overrightarrow{c^{\prime}}}\in\text{im}\ L_{G_{\phi}}$
Figure 3. Firing a vertex in a signed graph.

The matrix $L=L_{G_{\phi}}$ also defines an equivalence relation on integer
vectors. Namely for $\vec{c}_{1},\vec{c}_{2}\in{\mathbb{Z}}^{n}$ we say that

$\vec{c}_{1}\sim_{L}\vec{c}_{2}\text{ if and only if
}\vec{c}_{2}=\vec{c}_{1}-L\vec{z},\text{ for some
$\vec{z}\in{\mathbb{Z}}^{n}$}.$

In other words, $\vec{c}_{1}$ and $\vec{c}_{2}$ are equivalent if there exists
some sequence of fires (or reverse-fires) which takes $\vec{c}_{1}$ to
$\vec{c}_{2}$. The equivalence relation defined by $L$ leads to the following
notion of a critical group of $G_{\phi}$.

######  Definition 2.7.

Suppose $G_{\phi}$ is a signed graph with nonsink vertices
$v_{1},\dots,v_{n}$, and let $L=L_{G_{\phi}}$ denote its reduced signed
Laplacian. The _critical group_ of $G_{\phi}$ is the abelian group

${\mathcal{K}}(G_{\phi})={\mathbb{Z}}^{n}/\operatorname{im}L.$

One can see that the matrix $L$ has rank $n$ by applying [25, Theorem 8A.4].
From this it follows that ${\mathcal{K}}(G_{\phi})$ is a finite group of order
$|\mathcal{K}(G_{\phi})|=\det(L)$.

######  Remark 2.8.

To compute the critical group of a signed graph $G_{\phi}$ one can perform
integral row and column operations on the matrix $L_{G_{\phi}}$ to obtain its
_Smith normal form_ :

$\begin{pmatrix}p_{1}&0&0&\dots&0\\\ 0&p_{2}&0&\dots&0\\\ 0&0&p_{3}&\dots&0\\\
\vdots&\vdots&\vdots&\ddots&0\\\ 0&0&0&\dots&p_{n}\end{pmatrix}.$

In this case the diagonal elements satisfy $p_{i}|p_{i+1}$ for all
$i=1,\dots,n-1$ and are called the _invariant factors_. It then follows that

$\mathcal{K}(G_{\phi})\cong\mathbb{Z}/p_{1}\mathbb{Z}\oplus...\oplus\mathbb{Z}/p_{n}\mathbb{Z}.$

######  Remark 2.9.

Note that if $G$ has sink $q$ and $G\backslash\\{q\\}$ has more than one
component, then the reduced Laplacian $L$ has a block matrix form. Row
operations preserve this property, implying that the critical group
${\mathcal{K}}(G)$ is a direct sum of the critical groups of the underlying
subgraphs. Hence in our computations of ${\mathcal{K}}(G)$ we can assume that
$G\backslash\\{q\\}$ is connected.

By the Matrix Tree Theorem for signed graphs 2.5, the order of
${\mathcal{K}}(G_{\phi})$ also has a combinatorial interpretation. We note
that ${\mathcal{K}}(G_{\phi})$ (and even its order, given by $\det(L)$)
depends on the choice of sink vertex $q$.

Our goal in this paper is to study the structure and dynamics of the critical
group of a signed graph $G_{\phi}$ in terms of various notions of stability,
in analogy with the theory for graphs. One could study the dynamics of chip-
firing defined by $L_{G_{\phi}}$ using nonnegative configurations, but it is
not hard to see that the desired definitions break down. In particular one
does not have a natural representative for each element of
${\mathcal{K}}(G_{\phi})$.

######  Example 2.10.

Let $-C_{3}$ denote the 3-cycle with a single negative edge incident to the
nonsink vertices. First note that

$L_{-C_{3}}=\begin{pmatrix}2&1\\\ 1&2\end{pmatrix}$

and so $|{\mathcal{K}}(-C_{3})|=3$. If we allow all nonnegative vectors as
valid configurations, we obtain an infinite collection of critical
configurations in a single element of ${\mathcal{K}}(-C_{3})$. To see this
first note that all configurations of the form $(n,0)^{T}$ or $(0,n)^{T}$,
where $n\in\mathbb{Z}_{\geq 0},$ are both critical and $z$-superstable. One
can then check that all vectors of the form $(1+3k,0)$ are in the same
equivalence class determined by $L_{-C_{3}}$.

Hence the naive approach of using the signed Laplacian to define chip-firing
on nonnegative integer configurations fails. However, signed graphs provide a
natural setting to employ a theory of chip-firing on general invertible
matrices developed in [14]. We review the basics of this theory next.

###  2.3. Chip-firing on invertible matrices

In [14] Guzmán and Klivans develop a theory of chip-firing involving arbitrary
invertible matrices. Here one fixes an $n\times n$ invertible matrix $L$, as
well as an $n\times n$ $M$-matrix $M$. To recall the concept of an $M$-matrix,
we have the following characterization from [12, 21].

######  Definition 2.11.

Suppose $M$ is an $n\times n$ matrix such that $(M)_{ii}>0$ for all $i$ and
$(M)_{ij}\leq 0$ for all $i\neq j$. Then $M$ is called an (invertible) _$M$
-matrix_ if any of the following equivalent conditions hold:

  1. (1)

$M$ is avalanche finite;

  2. (2)

The real part of the eigenvalues of $M$ are positive;

  3. (3)

The entries of $M^{-1}$ are non-negative;

  4. (4)

There exists a vector $\vec{x}\in{\mathbb{R}}^{n}$ with ${\vec{x}}\geq\vec{0}$
such that $M\vec{x}$ has all positive entries.

The chip-firing model is determined by the choice of the pair $(L,M)$, which
we call a _chip-firing pair_. The relevant (chip) _configurations_
$\vec{c}\in\mathbb{Z}^{n}$ are simply integer vectors with $n$ entries, and
chip-firing is dictated by the matrix $L$. In this context the notion of a
‘valid’ configuration takes on a new meaning.

######  Definition 2.12.

Suppose $(L,M)$ is a chip-firing pair. A configuration $\vec{c}$ is _valid_ if
$\vec{c}\in S^{+}$, where

$S^{+}=\\{LM^{-1}\vec{x}:LM^{-1}\vec{x}\in\mathbb{Z}^{n},\vec{x}\in\mathbb{R}^{n}_{\geq
0}\\}.$

Equivalently, a configuration $\vec{c}$ is valid if $ML^{-1}\vec{c}\in R^{+}$,
where

$R^{+}=\\{\vec{x}\in\mathbb{R}^{n}_{\geq
0}:LM^{-1}\vec{x}\in\mathbb{Z}^{n}\\}.$

Recall that in the classic theory of chip-firing on a graph, a configuration
$\vec{c}$ is valid (or _effective_) if each entry is a nonnegative integer (an
integer point in the nonnegative orthant of ${\mathbb{R}}^{n}$). Indeed, one
recovers chip-firing on a graph $G$ by choosing $(L,L)$ as the chip-firing
pair, where $L=L_{G}$ is the reduced Laplacian of $G$. We then see that
$S^{+}=\mathbb{Z}^{n}_{\geq 0}$ consists of integer vectors in the nonnegative
orthant. Next we collect some other relevant definitions from [14].

######  Definition 2.13.

Suppose $(L,M)$ is a chip-firing pair, and suppose that $\vec{c}\in S^{+}$ is
a valid configuration. A site $i\in\\{1,\dots,n\\}$ is _ready to fire_ if

$\vec{c}-L\vec{e}_{i}\in S^{+},$

so that the vector obtained by subtracting the $i$th row of $L$ from $\vec{c}$
is also valid.

Similarly, suppose $\vec{x}\in R^{+}$. Then a site $i\in\\{1,\dots,n\\}$ is
_ready to fire_ if

$\vec{x}-M\vec{e}_{i}\in R^{+}.$

A configuration $\vec{c}$ (in $S^{+}$ or $R^{+}$) is _stable_ if no site is
ready to fire.

Analogous to the superstable configurations of usual chip-firing we also need
to consider the notion of (multi) set-firing.

######  Definition 2.14.

Suppose $(L,M)$ is a chip-firing pair. A configuration $\vec{c}\in S^{+}$ is
_$z$ -superstable_ if

$\vec{c}-L\vec{z}\notin S^{+}$

for all nonzero $\vec{z}\in{\mathbb{Z}}^{n}_{\geq 0}$.

Similarly, a valid configuration $\vec{x}\in R^{+}$ is $z$-superstable if

$\vec{x}-M\vec{z}\notin R^{+}$

for all nonzero $\vec{z}\in{\mathbb{Z}}^{n}_{\geq 0}$.

A configuration $\vec{c}\in S^{+}$ (resp. $R^{+}$) is _$\chi$ -superstable_ if
we restrict the choice of vectors $\vec{z}$ to the set
$\\{0,1\\}^{n}\setminus\\{\vec{0}\\}$.

For a configuration $\vec{c}\in S^{+}$ (resp. $\vec{d}\in R^{+}$), we let
$\text{stab}_{S^{+}}(\vec{c})$ (resp. $\text{stab}_{R^{+}}(\vec{d})$) denote
the configuration obtained by firing all sites until no site is ready to fire.
By adapting the proof of [15, Theorem 2.2.2] one can see that both
$\text{stab}_{S^{+}}(\vec{c})$ and $\text{stab}_{R^{+}}(\vec{d})$ are unique.
If the context is clear we simply write $\textrm{stab}(\vec{x})$ for the
stabilization of the configuration $\vec{x}$.

######  Definition 2.15.

Suppose $(L,M)$ is a chip-firing pair. A configuration $\vec{c}\in S^{+}$ is
said to be _reachable_ if there exists a configuration $\vec{d}\in S^{+}$
satisfying

  1. (1)

$\vec{d}-L\vec{e}_{i}\in S^{+}$ for all $i=1,\dots,n$, and

  2. (2)

$\vec{c}=\vec{d}-\sum_{j=1}^{k}L\vec{e}_{i_{j}}$, where
$\vec{d}-\sum_{j=1}^{\ell}L\vec{e}_{i_{j}}\in S^{+}$ for all $\ell\leq k$.

Similarly, a configuration $\vec{x}\in R^{+}$ is reachable if the analogous
conditions hold for some $\vec{y}$ in $R^{+}$, where $M$ replaces the role of
$L$.

Hence $\vec{c}$ is reachable if it can be obtained from a sequence of legal
firings starting from a valid configuration $\vec{d}$, where any vertex of
$\vec{d}$ can be fired. With these preliminaries we can recall the notion of a
critical configuration.

######  Definition 2.16.

Suppose $(L,M)$ is a chip-firing pair. A configuration $\vec{c}\in S^{+}$ is
said to be _critical_ if it is stable and _reachable_. Similarly, a
configuration $\vec{c}\in R^{+}$ is said to be _critical_ if it is stable and
reachable.

As was the case for classical chip-firing, the matrix $L$ defines an
equivalence relation on integer vectors. Namely, for
$\vec{c},\vec{d}\in{\mathbb{Z}}^{n}$ we have $\vec{c}\sim_{L}\vec{d}$ if there
exists a vector $\vec{f}\in{\mathbb{Z}}^{n}$ such that
$\vec{d}=\vec{c}-L{\vec{f}}$. Similarly if
$\vec{x},\vec{y}\in{\mathbb{R}}^{n}$ we have $\vec{x}\sim_{M}\vec{y}$ if there
exists $\vec{z}\in{\mathbb{Z}}^{n}$ such that $\vec{y}=\vec{x}-M{\vec{z}}$. As
noted in [14], one can freely move between $S^{+}$ and $R^{+}$ when checking
for for equivalence and hence other properties. We record these results here.

######  Lemma 2.17.

Suppose $(L,M)$ is a chip-firing pair. Let $\vec{c}=LM^{-1}\vec{x}$, where
$\vec{x}\in R^{+}$ (so that $\vec{c}\in S^{+}$). Then for any
$\vec{d}=LM^{-1}\vec{y}$ with $\vec{y}\in R^{+}$, we have
$\vec{c}\sim_{L}\vec{d}$ if and only if $\vec{x}\sim_{M}\vec{y}$. From this we
conclude the following:

  1. (1)

$\vec{c}$ is stable if and only if $\vec{x}$ is stable.

  2. (2)

$\vec{c}$ is reachable if and only if $\vec{x}$ is reachable.

  3. (3)

$\vec{c}$ is critical if and only if $\vec{x}$ is critical.

  4. (4)

$\vec{c}$ is $z$-superstable if and only if $\vec{x}$ is $z$-superstable.

In a similar vein, stabilizations of configurations of signed graphs can be
thought of in terms of the underlying unsigned graph as follows.

######  Lemma 2.18.

Suppose $G_{\phi}$ is a signed graph with chip-firing pair $(L,M)$, and let
$\vec{b}$ and $\vec{c}$ be valid configurations. Then
$\textrm{stab}_{S^{+}}(\vec{b})=\vec{c}$ if and only if
$\textrm{stab}_{R^{+}}(ML^{-1}\vec{b})=ML^{-1}\vec{c}$.

###### Proof.

This follows from the fact that $\vec{c}$ is obtained by a legal firing
sequence from $\vec{b}$ on $G_{\phi}$ (there exists some $v$ such that
$\vec{b}-L\vec{e_{v}}=\vec{c}$) if and only if $ML^{-1}\vec{c}$ is obtained by
a legal firing from $ML^{-1}\vec{b}$ on $|G|$ (there exists some $v$ such that
$ML^{-1}\vec{b}-M\vec{e_{v}}=ML^{-1}\vec{c}$). ∎

Recall that the equivalence classes $[\vec{c}]_{L}$ defined by $\sim_{L}$ form
the elements of the critical group
${\mathcal{K}}(G_{\phi})={\mathbb{Z}}^{n}/\operatorname{im}L$. A main result
from [14] is the following.

######  Theorem 2.19.

[14, Theorems 3.5, 4.3, 5.5] Suppose $(L,M)$ is a chip-firing pair. Then there
exists exactly one z-superstable configuration and one critical configuration
in each equivalence class $[\vec{c}]_{L}$.

###  2.4. Our setup

We now fix a signed graph $G_{\phi}$ with sink vertex $q$ and nonsink vertices
$v_{1},\dots,v_{n}$, and let $G=|G|$ denote the underlying graph. Recall that
the reduced Laplacian $L=L_{G_{\phi}}$ naturally defines a chip-firing rule,
as well as a critical group
${\mathcal{K}}(G_{\phi}):={\mathbb{Z}}^{n}/\operatorname{im}L$. Since the
reduced Laplacian $L_{G}$ is an $M$-matrix we can employ the Guzmán-Klivans
theory.

######  Definition 2.20.

Suppose $G_{\phi}$ is a signed graph with sink vertex $q$ and underlying graph
$G$. Then $(L_{G_{\phi}},L_{G})$ forms a _chip-firing pair_ for $G_{\phi}$.

From the Guzmán-Klivans theory we obtain the notion of _critical_ and _$z$
-superstable_ configurations of a signed graph. Each equivalence class
$[\vec{c}]_{L}$ contains a unique valid critical and a unique valid
$z$-superstable.

Furthermore, we can recover the critical group $\mathcal{K}(G)$ in terms of
the critical configurations of $G$. In particular one can check that the
stablization of the sum of two critical configurations is again critical, so
that if $\vec{v}_{1},\vec{v}_{2}$ are critical configuration we have

$[\vec{v}_{1}]\oplus[\vec{v}_{2}]=[\text{stab}(\vec{v}_{1}+\vec{v}_{2})],$

provides a critical representative of the product.

###  2.5. Examples

We next consider two examples to illustrate our constructions.

First consider the signed graph $G_{\phi}$ depicted in Figure 4. For this
graph the relevant matrices $L=L_{G_{\phi}}$, $M=L_{G}$, and $LM^{-1}$ are
given below.

$L=\begin{pmatrix}2&+1&0\\\ +1&3&-1\\\ 0&-1&2\end{pmatrix};\quad\quad
M=\begin{pmatrix}2&-1&0\\\ -1&3&-1\\\ 0&-1&2\end{pmatrix};\quad\quad
LM^{-1}=\begin{pmatrix}\frac{3}{2}&1&\frac{1}{2}\\\
\frac{5}{4}&\frac{3}{2}&\frac{1}{4}\\\ 0&0&1\end{pmatrix}$

$q$$+$$+$$+$$-$$+$$v_{1}$$v_{2}$$v_{3}$ Figure 4. A signed graph $G_{\phi}$
with universal sink $q$.

Recall that the valid configurations for the chip-firing pair $(L,M)$ are the
integer points in the cone determined by the columns of $LM^{-1}$. One can
check that $\det L=8$, and integral row operations can be used to reduce $L$
to Smith normal form to show that $\mathcal{K}(G_{\phi})\cong\mathbb{Z}_{8}$.

We find that the critical configurations of this signed graph are

$\left\\{\begin{pmatrix}4\\\ 5\\\ 0\end{pmatrix},\begin{pmatrix}3\\\ 3\\\
1\end{pmatrix},\begin{pmatrix}4\\\ 5\\\ 1\end{pmatrix},\begin{pmatrix}4\\\
4\\\ 1\end{pmatrix},\begin{pmatrix}2\\\ 3\\\
0\end{pmatrix},\begin{pmatrix}3\\\ 4\\\ 1\end{pmatrix},\begin{pmatrix}3\\\
4\\\ 0\end{pmatrix},\begin{pmatrix}5\\\ 6\\\ 0\end{pmatrix}\right\\}$

Recall that Theorem 3.3 gives a criterion for checking if a valid
configuration is critical. Note that in this case
$\vec{a_{q}}=\begin{pmatrix}1\\\ 1\\\ 1\end{pmatrix}$ and
$ML^{-1}\vec{a_{q}}=\begin{pmatrix}0\\\ \frac{1}{2}\\\ 1\end{pmatrix}$. Hence
$\vec{a_{q}}$ is valid and we can apply Theorem 3.3. Next note that
$4L^{-1}\vec{a_{q}}=\begin{pmatrix}1\\\ 2\\\ 3\end{pmatrix}$ so we can take
$N_{0}=4$. The Theorem then says that a valid configuration $\vec{c}$ is
critical if and only $\vec{c}=\mbox{stab}_{S^{+}}(\vec{c}+4\vec{a_{q}})$. For
instance the fact that

$\begin{pmatrix}4\\\ 5\\\
0\end{pmatrix}=\mbox{stab}_{S^{+}}\left(\begin{pmatrix}4\\\ 5\\\
0\end{pmatrix}+4\vec{a_{q}}\right)$

verifies its criticality. A calculation shows that $\begin{pmatrix}4\\\ 5\\\
1\end{pmatrix}$, $\begin{pmatrix}3\\\ 4\\\ 0\end{pmatrix}$,
$\begin{pmatrix}5\\\ 6\\\ 0\end{pmatrix}$, and $\begin{pmatrix}4\\\ 4\\\
1\end{pmatrix}$ are the distinct generators of ${\mathcal{K}}(G_{\phi})$. One
can also check that

$\begin{pmatrix}3\\\ 3\\\ 1\end{pmatrix}\oplus\begin{pmatrix}3\\\ 3\\\
1\end{pmatrix}=\textrm{stab}\left(\begin{pmatrix}6\\\ 6\\\
2\end{pmatrix}\right)=\begin{pmatrix}3\\\ 3\\\ 1\end{pmatrix},$

so that $(3,3,1)^{T}$ describes the identity in ${\mathcal{K}}(G_{\phi})$.

The $z$-superstable configurations of $G_{\phi}$ turn out to be

$\left\\{\begin{pmatrix}1\\\ 1\\\ 1\end{pmatrix},\begin{pmatrix}0\\\ 0\\\
0\end{pmatrix},\begin{pmatrix}3\\\ 3\\\ 0\end{pmatrix},\begin{pmatrix}1\\\
1\\\ 0\end{pmatrix},\begin{pmatrix}2\\\ 3\\\
0\end{pmatrix},\begin{pmatrix}2\\\ 2\\\ 0\end{pmatrix},\begin{pmatrix}3\\\
4\\\ 0\end{pmatrix},\begin{pmatrix}2\\\ 2\\\ 1\end{pmatrix}\right\\}.$

These have been listed so that they are in the same equivalence class as the
corresponding critical configurations listed above.

We next consider the signed graph $H_{\phi}$, depicted in Figure 5. For this
graph the relevant matrices $L=L_{H_{\phi}}$, $M=L_{|H|}$, and $LM^{-1}$ are
given below.

$L=\begin{pmatrix}3&+1&-1\\\ +1&2&-1\\\ -1&-1&3\end{pmatrix};\quad\quad
M=\begin{pmatrix}3&-1&-1\\\ -1&2&-1\\\ -1&-1&3\end{pmatrix};\quad\quad
LM^{-1}=\begin{pmatrix}2&2&1\\\ \frac{5}{4}&2&\frac{3}{4}\\\
0&0&1\end{pmatrix}$

$q$$+$$+$$+$$-$$+$$v_{1}$$v_{2}$$v_{3}$ Figure 5.  An example of a signed
graph $H_{\phi}$ where $|{\mathcal{K}}(H_{\phi})|$ is strictly larger than the
number of spanning trees of the underlying graph.

One can check that $\det L=12$, so that $|{\mathcal{K}}(H_{\phi})|$ is
strictly larger than the number of spanning trees of the underlying graph $H$.
Integral row operations on $L$ can be used to reduce $L$ to Smith normal form
to show that $\mathcal{K}(H_{\phi})\cong\mathbb{Z}_{12}$.

We find that the critical configurations of this signed graph are

$\left\\{\begin{pmatrix}7\\\ 6\\\ 2\end{pmatrix},\begin{pmatrix}8\\\ 6\\\
2\end{pmatrix},\begin{pmatrix}8\\\ 6\\\ 1\end{pmatrix},\begin{pmatrix}6\\\
5\\\ 2\end{pmatrix},\begin{pmatrix}7\\\ 5\\\
1\end{pmatrix},\begin{pmatrix}9\\\ 7\\\ 0\end{pmatrix},\begin{pmatrix}6\\\
4\\\ 2\end{pmatrix},\begin{pmatrix}7\\\ 5\\\
2\end{pmatrix},\begin{pmatrix}9\\\ 7\\\ 2\end{pmatrix},\begin{pmatrix}9\\\
7\\\ 1\end{pmatrix},\begin{pmatrix}8\\\ 6\\\
0\end{pmatrix},\begin{pmatrix}6\\\ 4\\\ 1\end{pmatrix}\right\\}.$

Note that in this case $\vec{a_{q}}=\begin{pmatrix}1\\\ 0\\\ 1\end{pmatrix}$
and $ML^{-1}\vec{s}=\begin{pmatrix}1\\\ -1\\\ 1\end{pmatrix}$, so that
$\vec{s}$ is not valid and hence Theorem 3.3 cannot be employed. A calculation
shows that $\begin{pmatrix}7\\\ 6\\\ 2\end{pmatrix}$, $\begin{pmatrix}8\\\
6\\\ 1\end{pmatrix}$, $\begin{pmatrix}9\\\ 7\\\ 0\end{pmatrix}$, and
$\begin{pmatrix}6\\\ 4\\\ 1\end{pmatrix}$ are the distinct generators of
${\mathcal{K}}(H_{\phi})$.

The $z$-superstable configurations of $H_{\phi}$ turn out to be

$\left\\{\begin{pmatrix}7\\\ 5\\\ 0\end{pmatrix},\begin{pmatrix}2\\\ 2\\\
0\end{pmatrix},\begin{pmatrix}5\\\ 4\\\ 0\end{pmatrix},\begin{pmatrix}6\\\
4\\\ 0\end{pmatrix},\begin{pmatrix}4\\\ 3\\\
0\end{pmatrix},\begin{pmatrix}5\\\ 4\\\ 2\end{pmatrix},\begin{pmatrix}0\\\
0\\\ 0\end{pmatrix},\begin{pmatrix}1\\\ 1\\\
0\end{pmatrix},\begin{pmatrix}3\\\ 3\\\ 0\end{pmatrix},\begin{pmatrix}6\\\
5\\\ 0\end{pmatrix},\begin{pmatrix}4\\\ 3\\\
2\end{pmatrix},\begin{pmatrix}3\\\ 2\\\ 0\end{pmatrix}\right\\}.$

We have listed these $z$-stable configurations so that they are in the same
equivalence class as the corresponding critical configurations listed above.
We can now consider the inverse image of these $z$-superstable configurations
under $LM^{-1}$, to obtain elements of $R^{+}$.

$\left\\{\begin{pmatrix}\frac{8}{3}\\\ \frac{5}{6}\\\
0\end{pmatrix},\begin{pmatrix}0\\\ 1\\\
0\end{pmatrix},\begin{pmatrix}\frac{4}{3}\\\ \frac{7}{6}\\\
0\end{pmatrix},\begin{pmatrix}\frac{8}{3}\\\ \frac{1}{3}\\\
0\end{pmatrix},\begin{pmatrix}\frac{4}{3}\\\ \frac{2}{3}\\\
0\end{pmatrix},\begin{pmatrix}\frac{2}{3}\\\ \frac{5}{6}\\\
2\end{pmatrix},\begin{pmatrix}0\\\ 0\\\ 0\end{pmatrix},\begin{pmatrix}0\\\
\frac{1}{2}\\\ 0\end{pmatrix},\begin{pmatrix}0\\\ \frac{3}{2}\\\
0\end{pmatrix},\begin{pmatrix}\frac{4}{3}\\\ \frac{5}{3}\\\
0\end{pmatrix},\begin{pmatrix}\frac{2}{3}\\\ \frac{1}{3}\\\
2\end{pmatrix},\begin{pmatrix}\frac{4}{3}\\\ \frac{1}{6}\\\
0\end{pmatrix}\right\\}.$

Recall that Proposition 3.8 gives a way to detect $z$-superstability of a
configuration $\vec{c}\in S^{+}$ by comparing $ML^{-1}\vec{c}\in R^{+}$ with
the superstable configurations of the underlying graph $|H|$. For instance we
see that $\vec{c}=\begin{pmatrix}1\\\ 1\\\ 0\end{pmatrix}$ is $z$-superstable
for $H_{\phi}$, since $ML^{-1}\vec{c}=\begin{pmatrix}0\\\ \frac{1}{2}\\\
0\end{pmatrix}$ is bounded above by the superstable configuration
$\begin{pmatrix}0\\\ 1\\\ 0\end{pmatrix}$ of $|H|$.

###  2.6. Relation to other critical groups

There is another way to define a critical group of a signed graph, for
instance studied by Reiner and Tseng in [23] based on work of Bacher et al
[1]. We discuss the main ideas here and refer to [1] and [23] for details. The
definition is inspired by the following construction of a ‘critical group’ for
any $r$-dimensional rational subspace
$\Lambda^{\mathbb{R}}\subset{\mathbb{R}}^{m}$. Let
$\Lambda=\Lambda^{\mathbb{R}}\cap{\mathbb{Z}}^{m}$ denote the underlying
lattice and let $\Lambda^{\\#}$ denote its _dual lattice_

$\Lambda^{\\#}:=\\{x\in\Lambda^{\mathbb{R}}:\langle
x,\lambda\rangle\in{\mathbb{Z}}\text{ for all $\lambda\in\Lambda$}\\}.$

The quotient $\Lambda^{\\#}/\Lambda$ is called the _determinant group_ of
$\Lambda$. Given any orthogonal decomposition of Euclidean space
${\mathbb{R}}^{m}=B^{\mathbb{R}}\oplus Z^{\mathbb{R}}$ we obtain two
determinant groups which turn out be isomorphic to the group

$\mathcal{C}_{BZ}:={\mathbb{Z}}^{m}/(B\oplus Z).$

To compute ${\mathcal{C}}_{BZ}$ we can use either an integral basis
$\\{b_{1},\dots,b_{r}\\}$ of $B$ or an integral basis
$\\{z_{1},\dots,z_{s}\\}$ of $Z$. For this let $M_{B}$ and $M_{Z}$ be the
matrices with columns given by those vectors. In what follows we use
$G(A):=A^{T}A$ to denote the _Gram matrix_ of a matrix $A$. We then get

$\mathcal{C}_{BZ}\cong\text{coker}(G(M_{Z}))\cong\text{coker}(G(M_{B})).$

The canonical example of this construction comes from the decomposition of
${\mathbb{R}}^{E}$ given by the incidence matrix $\delta$ of a graph
$G=(V,E)$. The row space of $\delta$ is called the _cut space_ , and the null
space (which is always orthogonal to the row space) is called the _cycle
space_. Since the integral cut space of any connected graph has an integral
basis given by the vertex cuts of any subset of $n-1$ vertices, this
construction recovers the usual critical group ${\mathcal{K}}(G)$. In
particular the relevant Gram matrix is simply the reduced Laplacian $L_{G}$
(for some choice of sink vertex). One can also take the integral _cycle_ space
of $G$ to recover ${\mathcal{K}}(G)$, as was studied in [11].

In [23] the authors use this approach to define a critical group
${\mathcal{C}}(G_{\phi})$ of a signed graph $G_{\phi}$. We let $\delta$ denote
the signed incidence matrix of $G_{\phi}$ and define

${\mathcal{C}}(G_{\phi})=\operatorname{im}\delta/\operatorname{im}\delta\delta^{T}=\operatorname{im}\delta/\operatorname{im}\tilde{L},$

where $\tilde{L}=\tilde{L}_{G_{\phi}}$ is the signed (but non-reduced)
Laplacian of $G_{\phi}$.

If $G_{\phi}$ is connected and has all positive edges, one can check that
$\delta$ has Smith normal with diagonal entries $(1,1,\dots,1,0)$, and
similarly the Smith normal form of $\tilde{L}$ has a $0$ in the bottom right.
Hence one can compute ${\mathcal{C}}(G_{\phi})$ by reading off the nonzero
entries in the Smith normal form of $\tilde{L}$. The critical group
${\mathcal{C}}(G_{\phi})$ has pleasing functorial properties and also connects
to the _double cover_ of graphs associated to $G_{\phi}$. We refer to [23] for
details.

The critical group ${\mathcal{K}}(G_{\phi})$ that we study in this paper more
closely connects to the notion of ‘adding critical configurations’, and also
has the property that its order $|{\mathcal{K}}(G)|$ is given by $\det
L_{G_{\phi}}$. To see how the two constructions differ, consider the signed
graph $G_{\phi}$ given by a $3$-cycle with a single negative edge between the
nonsink vertices. In this case the reduced signed Laplacian $L=L_{G_{\phi}}$
is given by

$L=\begin{bmatrix}2&1\\\ 1&2\end{bmatrix}.$

Note that $\det(L)=3$ so we expect $|{\mathcal{K}}(G_{\phi})|=3$. Indeed one
can check (see Section 4) that
$\mathcal{K}(G_{\phi})\cong{\mathbb{Z}}/3{\mathbb{Z}}$. On the other hand, a
simple computation shows that
$\mathcal{C}(G_{\phi})\cong{\mathbb{Z}}/2{\mathbb{Z}}$ .

##  3\. Stability Results

We next turn to proofs of our main results regarding critical and
$z$-superstable configurations of signed graphs. Recall that for a signed
graph $G_{\phi}$ we let $L=L_{G_{\phi}}$ denote the Laplacian of $G_{\phi}$,
and we let $M=L_{G}$ denote the Laplacian of the underlying graph. We first
show that the valid configurations for signed graphs never have negative
entries.

######  Proposition 3.1.

For any signed graph $G_{\phi}$, the set of valid configurations determined by
the chip-firing pair $(L,M)$ is contained in the nonnegative orthant.

###### Proof.

Recall that the columns of $LM^{-1}$ define the cone of the valid
configurations. Since $L$ is obtained from $M$ by changing some non-diagonal
$-1$ entries to $+1$, we can write $L=M+N,$ where

$(N)_{i,j}=\begin{cases}2,&\text{ if }L_{i,j}=+1\\\ 0,&\text{ otherwise.
}\end{cases}.$

Hence $LM^{-1}=(M+N)M^{-1}=MM^{-1}+NM^{-1}.$ Since $M$ is an $M$-matrix, we
have that $M^{-1}$ has nonnegative entries. The same is true for $MM^{-1}=I$
as well as for $N$, so that $LM^{-1}$ has all nonnegative entries and the
claim follows. ∎

###  3.1. Detecting criticality and firing the sink

We next turn to the proof of Theorem 3.3. For this we will need the following
observation regarding chip-firing on unsigned graphs.

######  Lemma 3.2.

Suppose $G$ is a graph with sink $q$ and nonsink vertices
$\\{v_{1},\dots,v_{n}\\}$ such that $G\backslash\\{q\\}$ is connected. Let
$\vec{c}\in\mathbb{Z}^{n}_{\geq 0}$ be a valid configuration such that
$(\vec{c})_{k}>0$ for some $k$. Then there exists an integer $N>0$ and firing
sequence on $N\vec{c}$ that yields a valid configuration $\vec{b}$ with the
property

$(\vec{b})_{i}\geq\deg(v_{i}),\text{ for all }i\in\\{1,2,...,n\\}.$

###### Proof.

Let $\ell$ be the maximum length of a path from $v_{k}$ to any nonsink vertex
of $G$. Now partition the set of nonsink vertices into $V_{0}\sqcup
V_{1}\sqcup V_{2}\sqcup\dots\sqcup V_{\ell}$, where $w\in V_{j}$ if the
distance between $w$ and $v_{k}$ satisfies $d(w,v_{k})=j$. We prove the
following claim via induction on $j$: for each $j\in\\{0,....,\ell\\}$ there
exists an integer $N_{j}$ and a firing sequence on $N_{j}\vec{c}$ that yields
a configuration $\vec{b}$ satisfying $(\vec{b})_{i}\geq\deg(v_{i})$, for all
$v_{i}\in V_{0}\sqcup V_{1}\sqcup\dots\sqcup V_{j}$. For $j=0$, we can simply
set $N_{0}=\deg(v_{k})$. Now assume $j>0$. By induction there exists an
$N_{j-1}$ and a firing sequence on $N_{j-1}\vec{c}$ that yields a
configuration $\vec{b}$ where $(\vec{b})_{i}\geq\deg(v_{i})$, for all $i$ such
that $v_{i}\in V_{0}\sqcup V_{1}\sqcup\dots\sqcup V_{j-1}$. Now, if we fire
each vertex of $V_{j-1}$ once starting from $\vec{b}$, we get a valid
configuration $\vec{b}^{\prime}$ such that for all $i$ where $v_{i}\in V_{j}$
we have $(\vec{b}^{\prime})_{i}\geq 1$. Let $m$ denote the maximal degree
among the vertices of $V_{j}$. Then repeating these same firings on $m\vec{b}$
will yield a configuration $m\vec{b^{\prime}}$ where
$(m\vec{b^{\prime}})_{i}\geq\deg(v_{i})$ for all $i$ such that $v_{i}\in
V_{j}$. Summing this configuration with $\vec{b}$ yields a configuration
satisfying the desired inequalities for $j$. Hence we let
$N_{j}=(m+1)N_{j-1}$. The result follows from applying the claim to $j=\ell$.
∎

Now, we are ready to apply the above to prove Theorem 3.3. In what follows
recall for a signed graph $G_{\phi}$ with sink vertex $q$ we define the vector
$\vec{s}$ as

$(\vec{s})_{i}:=\begin{cases}1,&\text{ if }v_{i}\in G\text{ is a nonsink
vertex adjacent to }q\\\ 0,&\text{ otherwise.}\end{cases}$

######  Theorem 3.3.

Let $G_{\phi}$ be a signed graph with sink $q$. Suppose $\vec{s}$ is a valid
configuration and pick a positive integer $N_{0}$ such that
$L^{-1}(N_{0}\vec{s})\in\mathbb{Z}_{\geq 0}$. Then a configuration $\vec{c}\in
S^{+}$ is critical if and only if
$\mbox{stab}_{S^{+}}(\vec{c}+N_{0}\vec{s})=\vec{c}$.

###### Proof.

We assume that $G\setminus\\{q\\}$ is a connected graph, and that $\vec{s}$ is
a valid configuration, so that $ML^{-1}\vec{s}$ is nonnegative.

Since $M$ is an $M$-matrix we have that $M^{-1}$ has nonnegative entries, so
that $M^{-1}(ML^{-1}\vec{s})=L^{-1}\vec{s}$ also has nonnegative (rational)
entries. Choose any positive integer $N_{0}$ such that
$L^{-1}(N_{0}\vec{s})\in\mathbb{Z}^{n}_{\geq 0}$. It follows that
$ML^{-1}(N_{0}\vec{s})\in\mathbb{Z}^{n}_{\geq 0}$ since $M$ has integer
entries. To prove the theorem, by applying Lemmas 2.18 and 2.17, it suffices
to show that for our chosen $N_{0}$, and for any $\vec{c}\in S^{+}$, we have

$\textrm{stab}_{R^{+}}(ML^{-1}(\vec{c}+N_{0}(\vec{s})))=ML^{-1}\vec{c}\iff
ML^{-1}\vec{c}\mbox{ is critical in $R^{+}$}.$

$(\Rightarrow)$ We must show that $ML^{-1}\vec{c}$ is reachable. Recall that
$ML^{-1}(N_{0}\vec{s})$ has at least one positive entry, and hence by Lemma
3.2 there exists a positive integer $N_{0}^{\prime}$ and a firing sequence on
$N_{0}^{\prime}(ML^{-1}(N_{0}\vec{s}))$ that yields a configuration $\vec{b}$
with the property $(\vec{b})_{i}\geq\deg(v_{i})$, for all
$i\in\\{1,2,...,n\\}$.

By assumption, there exists a valid firing sequence that brings
$ML^{-1}\vec{c}+ML^{-1}(N_{0}(\vec{s}))$ to $ML^{-1}\vec{c}$. By repeating
this firing sequence $N_{0}^{\prime}$ times, we get

$\textrm{stab}_{R^{+}}(N_{0}^{\prime}(ML^{-1}(N_{0}\vec{s}))+ML^{-1}\vec{c})=ML^{-1}\vec{c}.$

Notice that the left hand side is equal to
$\textrm{stab}_{R^{+}}(\vec{b}+ML^{-1}\vec{c})$, from the way that $\vec{b}$
was defined. Thus, $ML^{-1}\vec{c}$ is reachable from a configuration
$\vec{d}=\vec{b}+ML^{-1}\vec{c}\in R^{+}$ where
$(\vec{d})_{i}\geq\deg(v_{i})$. This implies that $ML^{-1}\vec{c}$ is
critical.

$(\Leftarrow)$ We assume that $ML^{-1}\vec{c}$ is a critical configuration in
$R^{+}$. By definition there exists a $\vec{d}\in R^{+}$ such that
$\textrm{stab}_{R^{+}}(\vec{d})=ML^{-1}\vec{c}$ and
$(\vec{d})_{i}\geq\deg(v_{i})$ for all $i\in\\{1,2,...,n\\}$. Next note that
for all $i\in\\{1,2,...,n\\}$, we have

$(\vec{d}+ML^{-1}(N_{0}\vec{s}))_{i}\geq\deg(v_{i})$

and that

$\textrm{stab}_{R^{+}}(\vec{d}+ML^{-1}(N_{0}\vec{s}))=\textrm{stab}_{R^{+}}(ML^{-1}\vec{c}+ML^{-1}(N_{0}\vec{s})).$

Therefore
$\vec{s}=\textrm{stab}_{R^{+}}(ML^{-1}\vec{c}+ML^{-1}(N_{0}\vec{s}))$ is a
critical configuration. Note that $ML^{-1}\vec{c}$ is also a critical
configuration, and in the same equivalence class as $\vec{s}$ since
$L^{-1}(N_{0}\vec{s})\in\mathbb{Z}^{n}$. The result follows. ∎

For certain signed graphs, we can explicitly compute the value of $N_{0}$ from
Theorem 3.3. In particular, we have the following.

######  Corollary 3.4.

Let $G_{\phi}$ be a signed graph with universal sink $q$. Suppose $G_{\phi}$
is signed-regular with $m_{-}$ negative edges incident to each nonsink vertex.
Then a valid configuration $\vec{c}$ is critical if and only if
$\vec{c}=\textrm{stab}(\vec{c}+(1+2m_{-})\vec{1})$.

###### Proof.

Let $\vec{s}$ denote the vector described above. Since $q$ is universal we
have that $\vec{s}=\vec{1}$, the vector of all $1$’s.

We will first show that $(2m_{-}+1)\vec{s}=(2m_{-}+1)\vec{1}$ is a valid
configuration, i.e. $(2m_{-}+1)\vec{1}\in S^{+}$. Note that since $G_{\phi}$
is signed-regular, then $G\backslash q$ is regular. Also since $q$ is
universal we have $M\vec{1}=\vec{1}$. Now note that

$ML^{-1}\vec{1}=M\left(\frac{1}{2m_{-}+1}\vec{1}\right)=\frac{1}{2m_{-}+1}\vec{1}\in\mathbb{R}^{n}_{\geq
0}.$

Thus $(2m_{-}+1)\vec{s}\in{\mathbb{Z}}^{n}_{\geq 0}$ is valid. Furthermore,
$(2m_{-}+1)\vec{s}$ is nonzero since $M$ and $L$ are invertible.

Now recall how $N_{0}$ was chosen from the proof of Theorem 3.3. We need to
pick $N_{0}$ such that $L^{-1}(N_{0}\vec{a_{q}})$ is a nonzero vector and ever
entry is a non-negative integer. Here we see $N_{0}=2m_{-}+1$ does the trick.
∎

Next we turn to the proof of Proposition 3.5, a generalization of the maximum
stable configuration of unsigned graphs.

######  Proposition 3.5.

Suppose $G_{\phi}$ is signed-regular with universal sink, such that each
nonsink vertex is incident to $m$ edges, with $m_{-}$ of them negative. If
$m^{\prime}=(m(2m_{-}+1)-1)$ then $m^{\prime}\vec{1}$ is a critical
configuration. Furthermore if $G_{\phi}=-G$, then any stable configuration
$\vec{c}$ satisfies $\vec{c}\leq m^{\prime}\vec{1}$.

###### Proof.

First we assume that $G_{\phi}$ is signed-regular with $m$ edges incident to
each nonsink vertex, $m_{-}$ of which are negative. As above we let
$m^{\prime}=m(2m_{-}+1)-1$.

We first prove that $m^{\prime}\vec{1}$ is a valid configuration, i.e. that
$ML^{-1}(m^{\prime}\vec{1})\geq 0$. This can be shown by first noting that

$L^{-1}(m^{\prime}\vec{1})=\frac{m^{\prime}}{2m_{-}+1}\vec{1}.$

Then, by properties of $G$ discussed above, we obtain that

$M\frac{m^{\prime}}{2m_{-}+1}\vec{1}=\frac{m^{\prime}}{2m_{-}+1}\vec{1}\geq\vec{0}$

This proves the validity of the configuration $m^{\prime}\vec{1}$.
Furthermore, the latter shows stability of $ML^{-1}(m^{\prime}\vec{1})$ in
$R^{+}$ and hence the stability of $m^{\prime}\vec{1}$ in $S^{+}$.

Next, we prove that $m^{\prime}\vec{1}$ is critical. From the previous
paragraph we have that $m^{\prime}\vec{1}$ is stable. To show that
$m^{\prime}\vec{1}$ is reachable, it is enough by Lemma 2.17 to show that its
preimage $ML^{-1}(m^{\prime}\vec{1})=\frac{m^{\prime}}{2m_{-}+1}\vec{1}$ is
reachable in $R^{+}$. Recall that $G$ is $m$-regular and hence $(m-1)\vec{1}$
is a critical configuration for $G$, and in particular is reachable. Since

$ML^{-1}(m^{\prime}\vec{1})=\left(\frac{m(2m_{-}+1)-1}{2m_{-}+1}\right)\vec{1}$

is componentwise greater than or equal to $(m-1)\vec{1}$, it is reachable as
well.

Now assume that $G_{\phi}=-G$, so that all edges not incident to the sink are
negative (and hence $m_{-}=m-1$). We claim that any other stable configuration
$\vec{c}\in S^{+}$ is componentwise smaller than $m^{\prime}\vec{1}$. For a
contradiction, suppose there exists $\vec{c}\in S^{+}$ has an entry greater
than $m^{\prime}=m(2m_{-}+1)-1$.

We claim there exists an entry of $L^{-1}\vec{c}$ that is at least $m$; we
know this since otherwise all entries of $\vec{c}=L(L^{-1}\vec{c})$ would be
less than $mm_{-}+m^{2}=m(m_{-}+m)=m(2m_{-}+1)=m^{\prime}+1$. Now let
$k=(L^{-1}\vec{c})_{i}$ be the largest entry of $(L^{-1}\vec{c})$ (so that in
particular $k\geq m$), and let $\vec{v}$ denote the $i$th row of $M$. The dot
product $\vec{v}\cdot(L^{-1}\vec{c})$ is then given by

$\vec{v}\cdot(L^{-1}\vec{c})\geq mk-(m-1)k=k\geq m,$

since we are assuming that all entries of $L^{-1}\vec{c}$ are less than $k$.
Hence the corresponding entry of $ML^{-1}\vec{c}$ is greater than $m$. Since
$\vec{c}$ is also valid, this implies that $ML^{-1}\vec{c}\in R^{+}$ is
unstable as it can be fired at the $i$th vertex. This means that $\vec{c}\in
S^{+}$ is unstable, and a contradiction is reached. ∎

###  3.2. Results on $z$-superstable Configurations

In this section, we establish our results on $z$-superstable configurations
for signed graphs. We begin with Theorem 3.6, which tells us that for any
signed graph the set of $z$-superstable configurations is the same as the set
of $\chi$-superstable configurations.

######  Theorem 3.6.

Suppose $G_{\phi}$ is a signed graph with sink $q$. Then a valid configuration
$\vec{c}\in S^{+}$ is $z$-superstable if and only if
$ML^{-1}\vec{c}-M\vec{z}\not\geq\vec{0}$ for any nonzero vector in
$\\{0,1\\}^{n}$.

###### Proof.

Here we follow the strategy employed in the proof of [13, Theorem 4.4]. Note,
however, that there is an error in the notation used in [13] which we attempt
to clarify here. From the definition, we know that if $\vec{c}$ is a
$z$-superstable configuration then it is also $\chi$-superstable, and hence we
only need to prove the converse.

For this suppose $\vec{c}\in S^{+}$ is $\chi$-superstable, so that
$ML^{-1}\vec{c}-M\vec{\chi}\not\geq\vec{0}$ for any vector 0-1 vector
$\vec{\chi}$. To establish the result it suffices to show that
$ML^{-1}\vec{c}-M\vec{z}\not\geq\vec{0}$ for any nonzero, nonnegative integer
vector $\vec{z}$. To that end, fix a nonzero vector
$\vec{z}\in\mathbb{N}^{n}$. For brevity let $\vec{x}=ML^{-1}\vec{c}$.

Now we construct a 0-1 vector $\vec{\chi}$ as follows. Let $\max(\vec{z})$
denote the maximum value of the entries of $z$, and for each $j$ such that
$(\vec{z})_{j}=\max(\vec{z})$, we set $(\vec{\chi})_{j}=1$ and
$(\vec{\chi})_{j}=0$ otherwise. By $\chi$-superstability of $\vec{x}\in
R^{+}$, there exists $j$ such that $(\vec{x}-M\vec{\chi})_{j}<0$. From
$(M\vec{\chi})_{j}>0$ and the definition of $M$, $(\vec{\chi})_{j}=1$. Note
that this construction of $\vec{\chi}$ makes it so that
$(\vec{z}-\vec{\chi})\geq\vec{0}$ and
$(\vec{z}-\vec{\chi})_{j}=\max(\vec{z}-\vec{\chi})$ for any $j$ such
$(\vec{\chi})_{j}=1$.

For $j$ such that $(\vec{x}-M\vec{\chi})_{j}<0$, we claim that
$(\vec{x}-M\vec{z})_{j}\leq(\vec{x}-M\vec{\chi})_{j}<0$. To see this it
suffices to show $(M(\vec{z}-\vec{\chi}))_{j}\geq 0$. By applying the fact
that $(\vec{\chi})_{j}=1$ and by the non-negative row-sum of $M$, we find that

$\displaystyle(M(\vec{z}-\vec{\chi}))_{j}$
$\displaystyle=\mbox{deg}(v_{j})\cdot(\vec{z}-\vec{\chi})_{j}-\sum_{k:\mbox{
$\\{v_{k},v_{j}\\}$ is an edge}}(\vec{z}-\vec{\chi})_{k}$
$\displaystyle=\mbox{deg}(v_{j})\cdot\max(\vec{z}-\vec{\chi})-\sum_{k:\mbox{
$\\{v_{k},v_{j}\\}$ is an edge}}(\vec{z}-\vec{\chi})_{k}$
$\displaystyle\geq(\max(\vec{z}-\vec{\chi}))\cdot\sum_{i}M_{j,i}$
$\displaystyle\geq 0$

This proves the claim. We conclude that $\vec{x}\in R^{+}$, and hence
$\vec{c}=LM^{-1}\vec{x}\in S^{+}$, is $z$-superstable. ∎

######  Remark 3.7.

Note that the results of Theorem 3.6 relies only on the fact that the matrix
$M=L_{G}$ has nonnegative row sums, as was the case in [13, Theorem 4.4].

We now establish a relationship between the $z$-superstable configurations of
a signed graph $G_{\phi}$ and those of its underlying unsigned graph $G$.

######  Proposition 3.8.

Let $G_{\phi}$ be a signed graph with sink $q$, and let $G$ denote its
underlying graph. Suppose $\vec{v}\in\frac{1}{\det L}{\mathbb{Z}}^{n}$ is a
vector such that $\vec{v}\leq\vec{w}$ for some superstable configuration
$\vec{w}$ of $G$. Then if $\vec{c}=LM^{-1}\vec{v}$ is valid we have that
$\vec{c}$ is $z$-superstable.

###### Proof.

Suppose $\vec{v}\in\frac{1}{\det L}{\mathbb{Z}}^{n}$ is a valid configuration
in $R^{+}$ such that $\vec{v}$ is coordinate-wise less than some superstable
configuration $\vec{\gamma}$ of $G$. By definition of superstability, we know
that for all nonzero $\vec{z}$ in $\mathbb{Z}_{\geq 0}^{n}$, we have
$\vec{\gamma}-M\vec{z}\not\geq\vec{0}$. Since $\vec{v}$ is componentwise less
than or equal to $\vec{\gamma}$, we see that for all nonzero
$\vec{z}\in\mathbb{Z}_{\geq 0}^{n}$, we get $\vec{v}-M\vec{z}\not\geq\vec{0}$.
Therefore, $LM^{-1}\vec{v}$ is $z$-superstable in $S^{+}$.

∎

###  3.3. Critical groups of signed graphs

We next gather some observations regarding critical groups of signed graphs.
The first observation is a connection between the identity of the critical
group of a signed graph $G_{\phi}$, and the identity of its unsigned
counterpart $G$.

######  Theorem 3.9.

Suppose $G_{\phi}$ is a signed graph with underlying graph $G$, and let
$L=L_{G_{\phi}}$ and $M=L_{G}$ denote the respective Laplacians. Let
$\vec{e}_{G}$ denote the identity of the critical group ${\mathcal{K}}(G)$.
Then the identity of ${\mathcal{K}}(G_{\phi})$ is given by

$\vec{e}_{G_{\phi}}=LM^{-1}\vec{e}_{G}.$

###### Proof.

We must show that $\vec{e}_{G_{\phi}}\in S^{+}$, is stable and reachable in
$G$, and $[\vec{e}_{G_{\phi}}]$ has order $1$ in ${\mathcal{K}}(G_{\phi})$ :
that is
$\textrm{stab}_{R^{+}}(\vec{e}_{G_{\phi}}+\vec{e}_{G_{\phi}})=\vec{e}_{G_{\phi}}$.

Since $\vec{e}_{G}\sim_{M}\vec{0},$ we have $\vec{e}_{G}=M\vec{v}$ for some
$\vec{v}\in\mathbb{Z}^{n}$. Thus,
$LM^{-1}\vec{e}_{G}=LM^{-1}\left(M\vec{v}\right)=L\vec{v}\in\mathbb{Z}^{n},$
since $L$ is an integer matrix. This gives us $LM^{-1}\vec{e}_{G}\in S^{+}$.
Now from Lemma 2.17 and Lemma 2.18, it suffices to show that $\vec{e}_{G}$ is
reachable, since it being stable and having order $1$ follows directly from
the fact that it is the identity of $\mathcal{K}(G)$. To see that
$\vec{e}_{G}$ is reachable, start from $\vec{e}_{G}$ and fire the bank
suitably many times to get a valid configuration with the property that it can
be fired at every non-sink vertex. ∎

We next show that the critical group of a signed graph is switching invariant.

######  Lemma 3.10.

Suppose $G_{\phi}$ and $G_{\psi}$ are signed graphs that are switching
equivalent. Then we have an isomorphism of critical groups

${\mathcal{K}}(G_{\phi})\cong{\mathcal{K}}(G_{\psi}).$

###### Proof.

It suffices to prove that claim for a single vertex switching. For this
suppose $G_{\psi}$ is obtained by switching the vertex of $G_{\phi}$
corresponding to row $i$ and column $i$ of the Laplacian $L_{G_{\phi}}$. Hence
the matrix $L_{G_{\psi}}$ is obtained from $L_{G_{\phi}}$ by changing each -1
in row $i$ and column $i$ to a 1, and vice versa. This is equivalent to
multiplying both row $i$ and column $i$ by $-1$ (which leaves the $i$th
diagonal entry unchanged). Since $-1$ is a unit in ${\mathbb{Z}}$ these
operations preserve the Smith normal form. The result follows from Remark 2.8.
∎

######  Corollary 3.11.

Suppose $G_{\phi}$ is a connected signed graph with sink $q$ such that
$G\backslash q$ is a tree. Then there exists an isomorphism of critical groups

${\mathcal{K}}(G_{\phi})\cong{\mathcal{K}}(|G|).$

###### Proof.

This follows from Lemmas 3.10 and 2.3. ∎

##  4\. Cycle Graphs

Having developed some results regarding chip-firing on signed graphs, we next
turn our attention to some concrete examples. In this section, we examine the
properties of signed cycle graphs.

We let $C_{n}$ denote the cycle graph on $n$ vertices with sink vertex
$q=v_{n}$ and nonsink vertices $v_{1},\dots,v_{n-1}$. Note that the reduced
Laplacian of $C_{n}$ is given by the $(n-1)\times(n-1)$ matrix $M=L_{C_{n}}$,
where

$M_{ij}=\begin{cases}2,&\mbox{$i=j$}\\\ -1,&\mbox{$|i-j|=1$}\\\
0,&\mbox{otherwise.}\end{cases}$

$q$$-$$-$$+$$+$$+$$-$ Figure 6. A signed cycle $(C_{6})_{\phi}$.

For any signed cycle $(C_{n})_{\phi}$ we hae the following.

######  Proposition 4.1.

Suppose $(C_{n})_{\phi}$ is any signed cycle on $n$ vertices. Then the
critical group satisfies

$\mathcal{K}((C_{n})_{\phi})\cong\mathbb{Z}_{n}.$

###### Proof.

Note that $C_{n}\backslash q$ is a path. Hence by Corollary 3.11, the critical
group is the same as that of $C_{n}$, which is known to be ${\mathbb{Z}}_{n}$
(see [15, Theorem 4.5.6]). ∎

Recall that for an (unsigned) graph $G$, there is a simple duality between the
critical configurations and superstable configurations. In particular, a
configuration $\vec{c}$ is critical if and only if
$\vec{c}_{\text{max}}-\vec{c}$ is superstable, where $\vec{c}_{\text{max}}$ is
the maximum stable configuration defined in Section 1.

In general it seems difficult to describe a similar duality for the case of
signed graphs. For the case of the all-negative odd cycle $-C_{2m+1}$,
however, we can recover such a result as described in Theorem 4.4. To
establish this duality, we employ a statistic on configurations of $-C_{2m+1}$
that is invariant under chip-firing and leads to an explicit description of
the critical group ${\mathcal{K}}(-C_{2m+1})$. The construction is inspired by
a similar statistic for unsigned cycles discussed in [9, Problem 1.2]. See
Figure 7 for an illustration of the case of $-C_{5}$.

$1({\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}2})-2({\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14}1})+3({\color[rgb]{0.49,0.83,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.49,0.83,0.13}3})-4({\color[rgb]{0.05,0.45,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.05,0.45,1}4})\equiv\
2\bmod 5\ \equiv\
1({\color[rgb]{0.05,0.44,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.05,0.44,1}4})-2({\color[rgb]{0.49,0.83,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.49,0.83,0.13}3})+3({\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14}1})-4({\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}2})$$q$$q$
Figure 7. An example of our statistic on signed odd cycles.

######  Lemma 4.2.

The map $f:{\mathcal{K}}(-C_{2m+1})\to\mathbb{Z}_{2m+1}$ defined by

$\begin{pmatrix}x_{1}\\\ \vdots\\\
x_{2m}\end{pmatrix}+\operatorname{im}L_{-C_{2m+1}}\mapsto\sum_{j=1}^{2m}(-1)^{j+1}jx_{j}\pmod{2m+1}$

is an isomorphism.

###### Proof.

To see that $f$ is well defined, any firing of a vertex (which decreases a
coordinate by $2$ and decreases the adjacent coordinate(s) by $1$ each)
preserves the value of the expression
$\sum_{j=1}^{2m}(-1)^{j+1}jx_{j}\pmod{2m+1}$. It is also clear that $f$ is a
homomorphism since the expression on the right-hand side is a linear
expression. The map $f$ is also surjective since for any
$a\in\mathbb{Z}_{2m+1}$, we have $a(\vec{e}_{1})$ in its pre-image. Combined
with $|{\mathcal{K}}(-C_{2m+1})|=2m+1$ from Proposition 4.1, we conclude that
$f$ is an isomorphism. ∎

We next show that all $z$-superstable configurations of $-C_{2m+1}$ share a
common property. We say that $\vec{c}\in{\mathbb{Z}}^{2m}$ is _palindromic_ if
for all $i=1,\dots,2m$ we have $(\vec{c})_{2m+1-i}=(\vec{c})_{i}$.

######  Lemma 4.3.

For all $m\geq 1$, each $z$-superstable configuration of $-C_{2m+1}$ is
palindromic.

###### Proof.

Assume $\vec{c}$ is $z$-superstable and let $\vec{d}$ be the configuration
obtained from $\vec{c}$ by flipping the coordinates:
$(\vec{d})_{2m+1-i}=(\vec{c})_{i}$ for all $i$. By symmetry of $-C_{2m+1}$, we
see that $\vec{d}$ is also $z$-superstable. Using $f$ from Lemma 4.2 we have
that $f(\vec{d})=f(\vec{c})$ since

$(-1)^{i}a\equiv(-1)^{2m+1-i}(2m+1-a)\pmod{2m+1}$

for any $i$ and $a\in\mathbb{Z}_{2m+1}$. Therefore $\vec{c}$ and $\vec{d}$ are
in the same equivalence class defined by $\operatorname{im}L_{-C_{2m+1}}$,
which by Theorem 2.19 implies that they are equal. Hence $\vec{c}$ has to be
palindromic. ∎

Finally we are ready to provide the proof of the duality.

######  Theorem 4.4.

Suppose $m\geq 1$ is an integer. Then the set map

$\Delta:\\{\mbox{z-superstable configurations of
$-C_{2m+1}$}\\}\to\\{\mbox{critical configurations of $-C_{2m+1}$}\\}$

given by $\vec{c}\mapsto\vec{e}_{-C_{2m+1}}+\vec{c}$ is a bijection.

###### Proof.

Let $\vec{c}$ be a $z$-superstable configuration. Our goal is to show that
$\vec{d}:=\vec{e}_{-C_{2m+1}}+\vec{c}$ is critical.

We first show that $\vec{d}$ is stable. Note that by Theorem 3.9 we have that
$ML^{-1}\vec{e}_{-C_{2m+1}}=\vec{e}_{C_{2m+1}}$. Using the method of [9,
Problem 1.2] one can check that $\vec{e}_{C_{2m+1}}=\vec{1}$. Recall that
$\vec{c}$ is palindromic via Lemma 4.3, and since $-C_{2m+1}$ is symmetric we
have that $ML^{-1}\vec{c}$ is also palindromic.

From $z$-superstability of $ML^{-1}\vec{c}$, it follows that set-firing
$\\{v_{j},\dots,v_{(2m+1)-j}\\}$ will not result in an allowable configuration
for any $1\leq j\leq m$.

If $j\neq 1$ we have

$ML^{-1}\vec{c}-M\left(\sum_{s=j}^{(2m+1)-j}\vec{e}_{s}\right)=ML^{-1}\vec{c}-\left(\vec{e}_{j}+\vec{e}_{(2m+1)-j}\right)+\left(\vec{e}_{j-1}+\vec{e}_{(2m+1)-(j-1)}\right)\not\geq
0,$

If $j=1$ we have

$ML^{-1}\vec{c}-M\left(\sum_{s=j}^{(2m+1)-j}\vec{e}_{s}\right)=ML^{-1}\vec{c}-\left(\vec{e}_{j}+\vec{e}_{(2m+1)-j}\right)\not\geq
0.$

This gives us $(ML^{-1}\vec{c})_{i}=(ML^{-1}\vec{c})_{(2m+1)-i}<1$ for all
$i$. This implies $(ML^{-1}\vec{d})_{i}<2$ for all $i$, giving us the
stability of $\vec{d}$.

It only remains to show the reachability of $\vec{d}$. Since
$\vec{e}_{-C_{2m+1}}$ is reachable, we can find some $\vec{b}$ that can be
fired at all vertices and stabilizes to $\vec{e}_{-C_{2m+1}}$. Since
$\vec{c}\in S^{+}$, we have that $\vec{b}+\vec{c}$ can be fired at all
vertices and stabilizes to $\vec{e}_{-C_{2m+1}}+\vec{c}=\vec{d}$ using the
same firing sequence.

∎

For even $n$, the map $f$ employed in Lemma 4.2 exhibits less predictable
behavior and we have been unable to demonstrate a similar duality. Hence we
ask the following.

######  Question 4.5.

Does there exist a duality between the set of critical and $z$-superstable
configurations of the negative cycles $-C_{n}$ for the case $n$ is even?

##  5\. Complete Graphs

In this section, we consider signed complete graphs $(K_{n})_{\phi}$. In
general, the critical group of such graphs seems to be quite complicated (for
instance the case of a single negative edge is still open), but we are able to
compute ${\mathcal{K}}((K_{n})_{\phi})$ for some classes.

Recall that from Lemma 3.10, the critical group only depends on the switching
class of the graph. Hence if $(K_{n})_{\phi}$ is switching equivalent to the
unsigned complete graph $K_{n}$, an extension of Cayley’s Theorem [15, Theorem
4.5.7] implies that
${\mathcal{K}}((K_{n})_{\phi})\cong{\mathcal{K}}(K_{n})\cong\mathbb{Z}_{n}^{n-2}$.

Next, we turn our attention to signed complete graphs that are switching
equivalent to $-K_{n}$. Recall that $-K_{n}$ denotes the _negative complete
graph_ , where all edges not incident to sink are negative. See Figure 8 for
an example.

$q$$+$$+$$+$$+$$+$$+$$+$$-$$-$$-$ Figure 8. A signed complete graph
$(K_{5})_{\phi}$ that is switching equivalent to $-K_{5}$.

######  Proposition 5.1.

Suppose $n\geq 3$ and let $(K_{n})_{\phi}$ be a signed complete graph that is
switching equivalent to $-K_{n}$. Then

${\mathcal{K}}((K_{n})_{\phi})\cong\mathbb{Z}_{n-2}^{n-3}\oplus\mathbb{Z}_{(n-2)(2n-3)}.$

###### Proof.

As observed above, it suffices to compute the critical group of $-K_{n}$. For
this note that the signed Laplacian $L=L_{-K_{n}}$ of $-K_{n}$ is given by

$L=(n-2)I_{n-1}-(-1)J_{n-1},$

where $I_{n-1}$ and $J_{n-1}$ are the $(n-1)\times(n-1)$ identity matrix and
an all-ones matrix, respectively. We apply the argument from [23, Corollary
7.6], which tells us that the invariant factors of $L$ are $1$, $n-2$, and
$(n-2)(2n-3)$, with $n-2$ having multiplicity of $n-3$. From this it follows
that $\mathbb{Z}^{n}/\mbox{im
}L\cong\mathbb{Z}_{n-2}^{n-3}\oplus\mathbb{Z}_{(n-2)(2n-3)}$, which completes
the proof. ∎

We remark that the integers $(n-1)(2n-1)$ are known as the _second hexagonal
numbers_ [20].

##  6\. Wheel Graphs

In this section we prove Theorem 6.9, which describes the critical groups of
signed wheel graphs. We begin by introducing the wheel graph and some
terminology.

######  Definition 6.1.

For $n\geq 3$, the _wheel graph_ $W_{n}$ is the graph with $n+1$ vertices
formed by connecting a universal sink vertex $q$ to all vertices of an
$n$-cycle.

We will use $v_{1},\ldots,v_{n}$ to label the nonsink vertices of $W_{n}$. See
Figure 9 for an example. The reduced Laplacian of the (unsigned) wheel $W_{n}$
is the $n\times n$ matrix given by

$(L_{W_{n}})_{ij}=\begin{cases}3,&\mbox{$i=j$}\\\ -1,&\mbox{$i\equiv(j+1)$ or
$i\equiv(j-1)\ (\mathrm{mod}\ n)$}\\\ 0,&\mbox{otherwise}.\end{cases}$

The reduced Laplacian of a signed wheel $(W_{n})_{\phi}$ is obtained from
changing the sign of the nondiagonal entries corresponding to negative edges.
As usual let $-W_{n}$ denote the signed wheel graph where all edges not
incident to the sink are negative.

$q$$v_{6}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ Figure 9. The wheel graph
$W_{6}$.

In [5] Biggs computed ${\mathcal{K}}(W_{n})$ for all $n$, and to recall his
results we review some well-known integer sequences.

######  Definition 6.2.

We let $f_{n}$ denote the $n$th _Fibonacci number_ , defined recursively by
$f_{n}=f_{n-1}+f_{n-2}$ with base cases $f_{0}=0,f_{1}=1$.

######  Definition 6.3.

We let $\ell_{n}$ denote the $n$th _Lucas number_ , defined recursively by
$\ell_{n}=\ell_{n-1}+\ell_{n-2}$ with base cases $\ell_{0}=2,\ell_{1}=1$.

The result of Biggs is the following.

######  Theorem 6.4 (Section 9 of [5]).

For any $n\geq 3$, the critical group of the unsigned wheel is given by:

$\mathcal{K}(W_{n})=\begin{cases}\mathbb{Z}_{f_{n}}\oplus\mathbb{Z}_{5f_{n}},&\mbox{$n$
is even}\\\ \mathbb{Z}_{\ell_{n}}\oplus\mathbb{Z}_{\ell_{n}},&\mbox{$n$ is odd
}.\end{cases}$

Theorem 6.9 is a generalization of Theorem 6.4 to signed wheel graphs. On the
way to proving Theorem 6.9 we first consider critical groups of negative
wheels $-W_{n}$. Here we get a uniform description that is independent of
parity of $n$.

######  Proposition 6.5.

For any $n\geq 3$, then we have $|\mathcal{K}(-W_{n})|=5f_{n}^{2}$.

###### Proof.

From Theorem 6.4 it follows that the order of the critical group (and hence
the number of spanning trees) of the unsigned wheel $W_{n}$ is

$|\mathcal{K}(W_{n})|=\begin{cases}5f_{n}^{2},&\mbox{$n$ is odd}\\\
\ell_{n}^{2},&\mbox{n is even.}\end{cases}$

If $n$ is even, we see that $-W_{n}$ is switching equivalent to $W_{n}$ by
performing a vertex switch at every other non-sink vertex. From Lemma 3.10 it
follows that $\mathcal{K}(-W_{n})=\mathcal{K}(W_{n})$ Hence,
$|\mathcal{K}(-W_{n})|=|\mathcal{K}(W_{n})|=5f_{n}^{2}$.

If $n$ is odd, using Theorem 2.6, we compute $\det(L_{-W_{n}})$ by counting
spanning TU-subgraphs. We see that the set of spanning TU-subgraphs of
$-W_{n}$ consists of the usual spanning trees of $W_{n}$ and a single subgraph
consisting of the exterior cycle of the wheel (along with the isolated vertex
$q$). From this count, we obtain that $\det(L_{-W_{n}})=\ell_{n}^{2}+4$. Since
$n$ is odd, Identity 53 from [3] tells us that $\ell_{n}^{2}+4=5f_{n}^{2}$. ∎

Using similar arguments, we can find the order of
$\mathcal{K}((W_{n})_{\phi})$ where $n\geq 2$ is even and $(W_{n})_{\phi}$ is
unbalanced.

######  Proposition 6.6.

Suppose $n\geq 2$ is even and $(W_{n})_{\phi}$ is an unbalanced signed wheel.
Then we have $|\mathcal{K}((W_{n})_{\phi})|=\ell_{n}^{2}$.

###### Proof.

From Lemma 2.3, we conclude that there are two switching equivalence classes
of $W_{n}$. In particular we can assume $(W_{n})_{\phi}$ has a single negative
edge incident to two non-sink vertices.

As in the proof of the previous Proposition, we use Theorem 2.6 and count the
spanning TU-subgraphs. As in $-W_{n}$ for odd $n$ case, the set of spanning
TU-subgraphs consists of the usual spanning trees of $W_{n}$ and a single
subgraph consisting of the exterior cycle of the wheel (along with the
isolated vertex $q$). From this count, we obtain that
$\mbox{det}(L)=5f_{n}^{2}+4$. Since $n$ is even, Identity 53 from [3] tells us
that $5f_{n}^{2}+4=\ell_{n}^{2}$. ∎

We next establish the structure of the critical group for unbalanced signed
graphs $(W_{n})_{\phi}$ for odd $n$. Since by Lemma 2.3 there are exactly two
switching equivalence classes of $W_{n}$, it suffices to analyze
$\mathcal{K}(-W_{n})$.

######  Lemma 6.7.

Let $m\geq 1$. Then we have

$\mathcal{K}(-W_{2m+1})\cong\mathbb{Z}_{f_{2m+1}}\oplus\mathbb{Z}_{5f_{2m+1}}.$

###### Proof.

For our argument we borrow techniques from Section 3 of [22], where the
authors computed the critical group of subdivided wheel graphs. We first show
that the critical group ${\mathcal{K}}(-W_{2m+1})$ has at most two generators.
For this let $L=L_{-W_{2m+1}}$, and suppose $\vec{x}=L\vec{z}$ for some
$\vec{z}\in\mathbb{Z}^{2m+1}$. Notice that $x_{i}+x_{i+2}=-3x_{i+1}$ for all
$i$, where the indices are considered modulo $2m+1$. From this, we can express
all $x_{i}$’s as a linear combination of $x_{1}$ and $x_{2}$, letting us
conclude that ${\mathcal{K}}(-W_{2m+1})$ has at most 2 generators. Writing
$x_{j}=a_{j}x_{2}-b_{j}x_{1}$ for each $j$, one can check that
$a_{1}=0,b_{1}=-1,a_{2}=1,b_{2}=0$, and $a_{j}:=(-1)^{j}f_{2j-2}$ and
$b_{j}:=(-1)^{j+1}f_{2j-4}$ for $j\geq 3$. Notice we can extend this to $j$
beyond $2m+1$ as well, so we have
$x_{1}=x_{2m+2}=a_{2m+2}x_{2}-b_{2m+2}x_{1}$.

Therefore, the Smith normal form of $L$ has $2m-1$ diagonal entries that have
value 1. From the previous paragraph, we have
$x_{1}=a_{2m+2}x_{2}-b_{2m+2}x_{1}$ and
$a_{2m+1}x_{2}-b_{2m+1}x_{1}=x_{2m+1}=-3x_{1}-x_{2}$. This tells us that one
only needs to evaluate the Smith normal form of

$A=\begin{pmatrix}a_{2m+2}&a_{2m+1}+1\\\
b_{2m+2}+1&b_{2m+1}-3\end{pmatrix}=\begin{pmatrix}f_{4m+2}&-f_{4m}+1\\\
-f_{4m}+1&f_{4m-2}-3\end{pmatrix}.$ (6.1)

Now, to find the Smith normal form of $A$, we need to find positive integers
$d_{1},d_{2}$ such that $d_{1}^{2}d_{2}=\mbox{det}(A)$ and
$d_{1}=\mbox{gcd}(f_{4m+2},f_{4m}-1,f_{4m-2}-3)$, see . The values $d_{1}$ and
$d_{1}d_{2}$ are the nontrivial invariant factors of the Smith normal form of
$A$ (and hence of $L$). Since all other diagonal entries of the Smith normal
form of $L$ is $1$, we also get that $d_{1}^{2}d_{2}=5f_{2m+1}^{2}$ thanks to
Proposition 6.5.

To find $d_{1}$, we utilize Identity 33 from [3], from which we obtain that
$f_{4m+2}=f_{2m+1}\ell_{2m+1}$. Furthermore, by consulting Equations 6 and 8
of [4], one can also obtain

$f_{4m}-1=f_{4m}-f_{2}=f_{2m+1}\ell_{2m-1}\text{ and
}f_{4m-2}-3=f_{4m-2}-f_{4}=f_{2m+1}\ell_{2m-3}.$

From the main theorem of [16], we have that
$\mbox{gcd}(\ell_{2m+1},\ell_{2m-1},\ell_{2m-3})=1$ for $m\geq 2$, and hence

$\mbox{gcd}(f_{4m+2},f_{4m}-1,f_{4m-2}-3)=\mbox{gcd}(f_{2m+1}\ell_{2m+1},f_{2m+1}\ell_{2m-1},f_{2m+1}\ell_{2m-3})=f_{2m+1}.$

Therefore we get $d_{1}=f_{2m+1}$ and $d_{2}=5$. We conclude that

$\mathcal{K}(-W_{2m+1})=\mathbb{Z}_{f_{2m+1}}\oplus\mathbb{Z}_{5f_{2m+1}}.$

∎

We now study the critical group of the unbalanced signed wheel for even
$n=2m$.

######  Lemma 6.8.

Suppose $m\geq 2$, and let $(W_{2m})_{\phi}$ be a signed even wheel where all
exterior edges except for one are negatively signed. Then,

$\mathcal{K}((W_{2m})_{\phi})=\mathbb{Z}_{\ell_{2m}}\oplus\mathbb{Z}_{\ell_{2m}}.$

###### Proof.

Without loss of generality, we suppose $(W_{2m})_{\phi}$ is the signed wheel
where the only positive edge of the graph is $\\{v_{2},v_{3}\\}$. The proof
will be similar to that of Lemma 6.7.

We first show that the critical group ${\mathcal{K}}((W_{2m})_{\phi})$ has at
most two generators. For this let $L=L_{(W_{2m})_{\phi}}$, and suppose
$\vec{x}=L\vec{z}$ for some $\vec{z}\in\mathbb{Z}^{2m}$. As before, notice
that $x_{i}+x_{i+2}=-3x_{i+1}$ for all $i$ except $i=1,2$ (where the indices
are considered modulo $2m$). We also have $x_{1}-x_{3}=-3x_{2}$ and
$-x_{2}+x_{4}=-3x_{3}$. From this, we can express all $x_{i}$’s as a linear
combination of $x_{1}$ and $x_{2}$, letting us conclude that
${\mathcal{K}}((W_{2m})_{\phi})$ has at most 2 generators. Writing
$x_{j}=a_{j}x_{2}-b_{j}x_{1}$ for each $j$, one can check that
$a_{1}=0,b_{1}=-1,a_{2}=1,b_{2}=0$, $a_{3}=3,b_{3}=-1$, and for $j\geq 3$ we
have $a_{j}=(-1)^{j+1}f_{2j-2}$ and $b_{j}=(-1)^{j}f_{2j-4}$. As before, we
can extend this to $j$ beyond $2m$ as well, so we have
$x_{1}=x_{2m+1}=a_{2m+1}x_{2}-b_{2m+1}x_{1}$.

Therefore, the Smith normal form of $L$ has $2m$ diagonal entries that have
value 1. From the previous paragraph, we have
$-3x_{2m}-x_{2m-1}=a_{2m+1}x_{2}-b_{2m+1}x_{1}$ and
$a_{2m}x_{2}-b_{2m}x_{1}=x_{2m}=-3x_{1}-x_{2}$. It then suffices to evaluate
the Smith normal form of

$A=\begin{pmatrix}a_{2m+1}&a_{2m}+1\\\
b_{2m+1}+1&b_{2m}-3\end{pmatrix}=\begin{pmatrix}f_{4m}&-f_{4m-2}+1\\\
-f_{4m-2}+1&f_{4m-4}-3\end{pmatrix}.$

Now, to find the nontrivial invariant factors of $L$ (and hence the Smith
normal form of $A$), as above we need to find positive integers $d_{1},d_{2}$
such that $d_{1}^{2}d_{2}=|\text{det}(A)|$ and
$d_{1}=\gcd(f_{4m},f_{4m-2}-1,f_{4m-4}-3)$. The $d_{1}$ and $d_{1}d_{2}$ are
the nontrivial invariant factors of the Smith normal form of $A$ and of $L$.
Since all other diagonal entries of the Smith normal form of $L$ are $1$, we
also get that $d_{1}^{2}d_{2}=\ell_{n}^{2}$ thanks to Proposition 6.6.

From Identity 33 from [3], we have $f_{4m}=f_{2m}\ell_{2m}$. Also by Equations
6 and 8 of [4], we have

$f_{4m-2}-1=f_{4m-2}-(-1)^{2m-2}f_{2}=f_{2m-2}\ell_{2m};$
$f_{4m-4}-3=f_{4m-4}-(-1)^{2m-4}f_{4}=f_{2m-4}\ell_{2m}.$

Hence $d_{1}=\gcd(f_{2m}\ell_{2m},f_{2m-2}\ell_{2m},f_{2m-4}\ell_{2m})$. An
application of Theorem 6 of [3] then gives us

$\text{gcd}(f_{2m},f_{2m-2},f_{2m-4})=f_{\text{gcd}(2m,2m-2,2m-4)}=f_{2}=1.$

Therefore, $d_{1}=\ell_{2m}$ and $d_{2}=1$. We conclude that

$\mathcal{K}((W_{2m})_{\phi})=\mathbb{Z}_{\ell_{2m}}\oplus\mathbb{Z}_{\ell_{2m}}.$

∎

We now combine our previous observations to provide a complete classification
of critical groups of signed wheels.

######  Theorem 6.9.

For any signed wheel $(W_{n})_{\phi}$ with $n\geq 3$ we have:

$\mathcal{K}((W_{n})_{\phi})=\begin{cases}\mathbb{Z}_{f_{n}}\oplus\mathbb{Z}_{5f_{n}},&\mbox{$n$
is odd and $(W_{n})_{\phi}$ is unbalanced}\\\
\mathbb{Z}_{\ell_{n}}\oplus\mathbb{Z}_{\ell_{n}},&\mbox{$n$ is even and
$(W_{n})_{\phi}$ is unbalanced}\\\
\mathbb{Z}_{\ell_{n}}\oplus\mathbb{Z}_{\ell_{n}},&\mbox{$n$ is odd and
$(W_{n})_{\phi}$ is balanced}\\\
\mathbb{Z}_{f_{n}}\oplus\mathbb{Z}_{5f_{n}},&\mbox{$n$ is even and
$(W_{n})_{\phi}$ is balanced}\end{cases}$

and this gives all possible critical groups of $(W_{n})_{\phi}$.

###### Proof.

Recall that a wheel $W_{n}$ has two switching equivalence classes. If
$(W_{n})_{\phi}$ is balanced, the result follows from Theorem 6.4, and
otherwise we use Lemmas 6.7 and 6.8. ∎

##  7\. Fan Graphs

In this section we prove Theorem 7.3, which describes the critical groups of
_fan graphs_. We can think of a wheel graph as adding a universal sink to a
cycle, and if we instead add a sink to a path we get the class of fan graphs
[6].

######  Definition 7.1.

For an integer $n\geq 3$, the fan graph $F_{n}$ is defined as the graph
obtained by adding a universal sink to a path graph on $n$ vertices.

$q$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ Figure 10. The fan graph $F_{5}$.

We use $v_{1},\ldots,v_{n}$ to label the vertices of the underlying path and
as usual use $q$ to denote the sink. In particular, $F_{n}$ is obtained from
the wheel graph $W_{n}$ by removing the edge between $v_{1}$ and $v_{n}$. See
Figure 10 for an illustration of $F_{5}$. The reduced Laplacian of $F_{n}$ is
the $n\times n$ matrix given by

$(L_{F_{n}})_{ij}=\begin{cases}2,&\mbox{$i=j\in\\{1,n\\}$}\\\
3,&\mbox{$i=j\notin\\{1,n\\}$}\\\ -1,&\mbox{$|i-j|=1$}\\\
0,&\mbox{otherwise}.\end{cases}$

Now suppose $(F_{n})_{\phi}$ is any signed fan. To prove Theorem 7.3 we as
usual first determine the order of $\mathcal{K}((F_{n})_{\phi})$.

######  Lemma 7.2.

For any signed fan $(F_{n})_{\phi}$ we have
$|\mathcal{K}((F_{n})_{\phi})|=f_{2n}$.

###### Proof.

First note that $F_{n}\backslash q$ is a path, so from Corollary 3.11 we have
$\mathcal{K}((F_{n})_{\phi})\cong\mathcal{K}(|F_{n}|)$. From the Matrix-Tree
Theorem, it then suffices to show that the number of spanning trees of $F_{n}$
is given by $f_{2n}$. For this we use induction on $n$.

Note that $F_{1}$ is a single edge and $F_{2}$ is a triangle, and hence the
result holds for $n=1,2$ (recall $f_{0}=0$ and $f_{1}=1$). Now suppose $n\geq
3$ and consider a spanning tree $T$. We let $e=\\{q,v_{1}\\}$ and consider two
cases. First suppose $T$ does not contain $e$. Then $T$ consists of the edge
$\\{v_{1},v_{2}\\}$ along with a spanning tree of the graph obtained by
removing $v_{1}$. Note that the subgraph induced by $v_{2},....,v_{n},q$ is
isomorphic to $F_{n-1}$ and hence by induction there are $f_{2n-2}$ such
trees.

Next suppose $T$ does contain $e$. This means that $T$ is the result of
adjoining path $q,v_{1},...,v_{i}$ for some $i$ and a spanning tree of the
subgraph induced by $v_{i+1},...v_{n},q$. Let $i$ be the largest index so that
the path $v_{1},\ldots,v_{i}$ is contained in $T$. If $i=n$ then $T$ is a
path. For $i<n$, when we remove the vertices $v_{1},\ldots,v_{i}$ we obtain a
spanning tree of an induced subgraph which is isomorphic to $F_{n-i}$. By
induction there are $1+\sum_{k=1}^{n-1}f_{2(n-k)}=f_{2n-1}$ spanning trees of
this form.

We conclude that there are $f_{2n-2}+f_{2n-1}=f_{2n}$ spanning trees of
$F_{n}$, which completes the proof. ∎

We next show that the critical group of a fan graph is cyclic, as usual via a
calculation of the Smith normal form of its Laplacian. The computation of
${\mathcal{K}}(F_{n})$ for the unsigned case is an exercise in [9, Exercise
2.8(e)], we include a complete proof here.

######  Theorem 7.3.

Let $(F_{n})_{\phi}$ be any signed fan graph where $n\geq 1$. Then
$\mathcal{K}((F_{n})_{\phi})\cong\mathbb{Z}_{f_{2n}}$.

###### Proof.

As discussed above, it suffices to determine the critical group
$\mathcal{K}(|F_{n}|)$. From Lemma 7.2 it is enough to show that the group is
cyclic, i.e. the Smith normal form of $L=L_{|F_{n}|}$ has at most one entry
that is larger than 1. For this suppose $\vec{x}=L\vec{z}$ for some
$\vec{z}\in\mathbb{Z}^{n}$. From our description of $L_{F_{n}}$ we have the
following relations:

$\begin{split}3x_{i}&=x_{i-1}+x_{i+1},\mbox{ for all
$i\in\\{2,3,...,n-1\\}$},\\\ 2x_{1}&=x_{2},\\\ 2x_{n}&=x_{n-1}.\end{split}$
(7.1)

Thus, for any $i\in\\{1,2,...,n\\}$ there exists an integer $b_{i}$ such that
$x_{i}=b_{i}x_{1}$. Thus the Smith normal form of $L$ has at most one
nontrivial diagonal entry, which from Lemma 7.2 must be $f_{2n}$. We conclude
that $\mathcal{K}(|F_{n}|)\cong\mathbb{Z}_{f_{2n}}$. ∎

While we were preparing this document we were made aware of related results of
Selig from [24]. Here the author also considers (unsigned) wheel and fan
graphs, and constructs bijections between the set of critical configurations
and various combinatorial objects that give an interpretation of the _level_
of the configuration. In this context the number of critical configurations of
level $k$ can be seen to correspond to a Tutte polynomial evaluation. As we
have seen, performing a single vertex switching preserves the number of
critical configurations and even the isomorphism type of the critical group
(see Lemma 3.10). However, the level sequence can change and it is an open
question to understand the resulting combinatorial structure.

##  8\. Further Directions

In this work we have initiated the study of chip-firing on signed graphs, but
many natural questions remain. In this section we discuss some possible
further directions of research.

One immediate question is whether there exist more efficient algorithms for
computing critical configurations and $z$-superstable configurations of signed
graphs. From Theorem 3.6 we have the observation that a configuration on a
signed graph $G_{\phi}$ is $z$-superstable if and only if it is stable under
set (as opposed to multiset) firings. This provides an upper bound on the
number of firings one must perform to check for $z$-superstability, but still
requires checking all subsets of the nonsink vertices and hence an exponential
number of steps. In the case of unsigned graphs, the well known Dhar’s Burning
Algorithm [10, 15] checks for superstability in a polynomial number of steps.

######  Question 8.1.

Does there exist a Burning Algorithm for signed graphs that checks whether a
given configuration is $z$-superstable?

We next turn to computing critical configurations. Recall that for unsigned
graphs we have a simple duality between critical and superstable
configurations (see Section 2.6.5 of [15]). Employing this duality, along with
Dhar’s Burning Algorithm, provides a polynomial time (in the number of
vertices) way to check if a given configuration is critical. For the case of
signed graphs, no simple correspondence seems to exist, although in Theorem
4.4 we have found some answers for a class of signed cycles. In general we are
looking for a bijection between two equinumerous sets of lattices points in a
certain cone.

######  Question 8.2.

Does there exist a duality between the set of $z$-superstable configurations
and the set of critical configurations, perhaps for some class of signed
graphs $G_{\phi}$?

We have seen in Lemma 3.10 that vertex switching preserves the critical group
of a signed graph. In particular, if a signed graph is obtained from another
via a vertex switching, both signed graphs have the same number of critical
and $z$-superstable configurations. However it is not clear how the set of
configurations themselves change, even in small examples.

######  Question 8.3.

If $G_{\psi}$ is obtained from $G_{\phi}$ via a vertex switching, can one
describe a bijection between the underlying critical (or $z$-superstable)
configurations?

We would also like to understand connections between chip-firing on signed
graphs and other combinatorial objects. In the case of chip-firing on a graph
$G$, recall that the superstable configurations coincide with the class of
$G$-parking functions (with the case of $G=K_{n}$ particularly well-studied).
By work of Merino [18] the underlying degree sequence (that is, the number of
superstable configurations of degree $i$) also relates to Tutte polynomial
evaluations and in particular _activity_ of spanning trees. It would be
interesting to understand the combinatorial properties of $z$-superstable
configurations of signed graphs.

######  Question 8.4.

For a signed graph $G_{\phi}$ (with chosen sink $q$), does the degree sequence
of $z$-superstable configurations have any combinatorial meaning?

In a related story, a number of bijections between $G$-parking functions and
spanning trees of a graph $G$ have been studied [8], generalizing Dhar’s
algorithm [10]. We would like to extend this story to the case of signed
graphs, where the set of spanning trees is replaced by the bases of the
underlying matroid, and where we ask for a _multijection_ in the sense of
[17].

In addition, we note that many of the constructions we discuss here can be
generalized to the setting of an arbitrary $M$-matrix. In the case of signed
graphs we used the reduced Laplacian $M=L_{G}$ of a graph $G$ and changed the
sign of certain off-diagonal entries (corresponding to negative edges) to
obtain the invertible matrix $L$. The same construction can be performed on an
arbitrary $M$-matrix $M$, and many of our results carry through. For instance,
we recover Proposition 3.1 as well as Theorem 3.6 for the case of $M$-matrices
with nonnegative row sums.

Even more generally, many of our results hold for the case of chip-firing on
the pair $(L,M)$, for an arbitrary invertible matrix $L$ and $M$-matrix $M$.
This includes Proposition 3.8 and Theorem 3.9. We see signed graphs as a
particularly natural case where one can apply the theory of chip-firing on a
pair $(L,M)$. We hope to further understand how phenomena observed in chip-
firing on graphs can be extended.

## Acknowledgements

This research was conducted as part of an REU at Texas State University during
Summer 2022, with funding from the NSA and NSF grant #1757233. We are grateful
to these organizations for their financial support and for providing a
fruitful work environment. We thank Carly Klivans for sharing her insights on
chip-firing.

## References

  * [1] Roland Bacher, Pierre de la Harpe, and Tatiana Nagnibeda.  The lattice of integral flows and the lattice of integral cuts on a finite graph.  Bull. Soc. Math. France, 125(2):167–198, 1997.
  * [2] R. B. Bapat.  Graphs and matrices.  Universitext. Springer, London; Hindustan Book Agency, New Delhi, 2010\.
  * [3] Arthur T. Benjamin and Jennifer J. Quinn.  Proofs that really count, volume 27 of The Dolciani Mathematical Expositions.  Mathematical Association of America, Washington, DC, 2003.  The art of combinatorial proof.
  * [4] G. E. Bergum and V. E. Hoggatt, Jr.  Sums and products for recurring sequences.  Fibonacci Quart., 13:115–120, 1975.
  * [5] N. L. Biggs.  Chip-firing and the critical group of a graph.  J. Algebraic Combin., 9(1):25–45, 1999.
  * [6] A. Brandstadt, V.B. Le, and J.P. Spinrad.  Graph Classes: A Survey.  Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 1999.
  * [7] Seth Chaiken.  A combinatorial proof of the all minors matrix tree theorem.  SIAM J. Algebraic Discrete Methods, 3(3):319–329, 1982.
  * [8] Denis Chebikin and Pavlo Pylyavskyy.  A family of bijections between $G$-parking functions and spanning trees.  J. Combin. Theory Ser. A, 110(1):31–41, 2005.
  * [9] Scott Corry and David Perkinson.  Divisors and sandpiles.  American Mathematical Society, Providence, RI, 2018.  An introduction to chip-firing.
  * [10] Deepak Dhar.  Self-organized critical state of sandpile automaton models.  Phys. Rev. Lett., 64:1613–1616, Apr 1990.
  * [11] Anton Dochtermann, Eli Meyers, Rahgav Samavedam, and Alex Yi.  Integral flow and cycle chip-firing on graphs.  Ann. Comb., 25(3):595–616, 2021.
  * [12] Andrei Gabrielov.  Asymmetric abelian avalanches and sandpiles.  Preprint, pages 93–65, 1994.
  * [13] Johnny Guzmán and Caroline Klivans.  Chip-firing and energy minimization on M-matrices.  J. Combin. Theory Ser. A, 132:14–31, 2015.
  * [14] Johnny Guzmán and Caroline Klivans.  Chip firing on general invertible matrices.  SIAM J. Discrete Math., 30(2):1115–1127, 2016.
  * [15] Caroline J. Klivans.  The mathematics of chip-firing.  Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2019.
  * [16] Wayne L. McDaniel.  The G.C.D. in Lucas sequences and Lehmer number sequences.  1991\.
  * [17] Alex McDonough.  A family of matrix-tree multijections.  Algebr. Comb., 4(5):795–822, 2021.
  * [18] Criel Merino López.  Chip firing and the Tutte polynomial.  Ann. Comb., 1(3):253–259, 1997.
  * [19] Ram Melkote Moore.  Chip-firing on signed graphs.  Bachelors Thesis, Texas State University, 2021.
  * [20] OEIS Foundation Inc.  Entry Aa014105 in the On-Line Encyclopedia of Integer Sequences, 2022.  https://oeis.org/A014105.
  * [21] R. J. Plemmons.  $M$-matrix characterizations. I. Nonsingular $M$-matrices.  Linear Algebra Appl., 18(2):175–188, 1977.
  * [22] Zahid Raza.  On the critical group of certain subdivided wheel graphs.  Punjab Univ. J. Math. (Lahore), 47(2):57–64, 2015.
  * [23] Victor Reiner and Dennis Tseng.  Critical groups of covering, voltage and signed graphs.  Discrete Math., 318:10–40, 2014.
  * [24] Thomas Selig.  Combinatorial aspects of sandpile models on wheel and fan graphs.  European J. Combin., 110:Paper No. 103663, 23, 2023.
  * [25] Thomas Zaslavsky.  Signed graphs.  Discrete Appl. Math., 4(1):47–74, 1982.