Frances Dean^a , Max Everett^b , Ralph Morrison^c

frances.e.dean2019@gmail.com, maxeverett1@gmail.com, 10rem@williams.edu

The divisorial gonality of a graph is the minimum degree of a positive rank divisor on that graph. We introduce the multiplicity-free gonality of a graph, which restricts our consideration to divisors that place at most 1 chip on each vertex. We give a sufficient condition in terms of vertexconnectivity for these two versions of gonality to be equal; and we show that no function of gonality can bound multiplicity-free gonality, even for simple graphs. We also prove that multiplicity-free gonality is NP-hard to compute, while still determining it for graph families for which gonality is currently unknown. We also present new gonalities, such as for the wheel graphs.

Keywords: chip-firing games, graph gonality Mathematics Subject Classification : 05C57

DOI: 10.5614/ejgta.2023.11.2.2

1. Introduction

Chip-firing games on graphs provide a discrete, combinatorial analog to divisor theory on algebraic curves. The theory of divisors on graphs mirrors that on algebraic curves through analogs of such results as the Riemann-Roch theorem [5] and results on graphs imply results on curves through Baker's specialization lemma [4]. This allows for purely combinatorial methods to prove theorems in algebraic geometry. This theory has been developed for both metric graphs and finite (non-metric) graphs. Throughout this paper we work with finite multigraphs, with multiple

Received: 12 March 2022, Revised: 29 January 2023, Accepted: 28 May 2023.

^aDepartment of Mathematics, University of California Berkeley, Berkeley, CA, USA

^bDepartment of Mathematics, City University of New York, New York, NY, USA

^cDepartments of Mathematics and Statistics, Williams College, Williamstown, MA 01267

edges allowed between vertices but no loops from a vertex to itself (if there are no multiple edges between any pair of vertices, the graph is called simple).

One much-studied invariant of curves, and more recently of graphs, is gonality (specified as divisorial gonality for graphs). In either setting, it can be defined as the minimum degree of a positive rank divisor; in the algebro-geometric world it is also the minimum degree of a surjective morphism from the curve to a projective line. In the graph theoretic world, gonality admits a description in terms of a game: Player A places k chips on the vertices of a graph, and Player B adds −1 chips. If Player A can perform certain "chip-firing" moves on the graph to eliminate debt, then Player A wins; if not, then Player B wins. The gonality of the graph can be defined as the minimum k such that Player A has a placement of k chips that wins against Player B, no matter how Player B plays. We note that there are a number of other definitions of graph gonality inequivalent to divisorial gonality, including stable gonality and stable divisorial gonality [7]. Throughout this paper "gonality" without a qualifier refers to divisorial gonality.

We introduce a variation of gonality which we call multiplicity-free gonality. Loosely speaking, a divisor is mutiplicity-free if it places either 0 or 1 chips on each vertex. The multiplicity-free gonality of the graph is then the minimum degree of a multiplicity-free divisor that wins the gonality game. It immediately follows that gonality is at most multiplicity-free gonality; we will see in Section 2 that there are graphs with multiplicity-free gonality strictly larger than gonality, such as the slashed ladder graph in Figure 1.

Figure 1. The 2 × 4 slashed ladder graph, with gonality strictly smaller than multiplicity-free gonality.

One reason for introducing multiplicity-free gonality is that it is in many ways more feasible to study than traditional gonality. Although both are NP-hard to compute (see [11] for gonality, and our Theorem 5.3 for multiplicity-free gonality), brute-force methods have to consider significantly fewer divisors for multiplicity-free gonality. Moreover, multiplicity-free gonality is much more amenable to proofs utilizing such techniques as Dhar's burning algorithm [9]; in Section 5 we will leverage this to compute the multiplicity-free gonality of an arbitrary ℓ-dimensional rook's graph, along with other graph families.

The question then becomes when are gonality and multiplicity-free gonality equal. We prove in Section 3 that if a simple graph has gonality equal to its vertex connectivity, then it also has gonality equal to multiplicity-free gonality. We also provide several negative results that show the limitations of relating gonality with multiplicity-free gonality. In Section 4 we prove that for graphs of any fixed gonality 2 or more, multiplicity-free gonality can take on any larger value, meaning that we cannot bound multiplicity-free gonality with a function of gonality; except when the fixed gonality is 2, we can achieve the same result even for simple graphs. We also show in Section 5 that for any r ≥ 4, there exists an r-regular graph with gonality strictly smaller than

multiplicity-free gonality; that section also includes our results on particular graph families, and our proof that multiplicity-free gonality is NP-hard to compute.

2. Background and initial results

A graph G = (V, E) is a finite collection of vertices V (G) with a finite multiset of edges E(G) connecting unordered pairs of vertices of V (G). Although we allow for multiple edges between two vertices, we do not allow loops from an edge to itself. A graph is connected if it is possible to travel from every vertex to every other vertex along edges. A set S ⊂ V (G) of vertices is called a vertex-cut if deleting the vertices in S from G yields either a disconnected graph, or a graph on one vertex; the minimum cardinality of a vertex-cut of G is called the vertex-connectivity κ(G) of G. The number of edges incident to a vertex v is called the valence¹ of v, denoted val(v). Given a subset U ⊂ V (G), the outdegree of U is the number of edges with one endpoint in U and the other endpoint in U C.

Letting G be a connected graph, we let Div(G) denote the free abelian group on the vertices of G; as a group, Div(G) is isomorphic to Z |V (G)| . Any element of Div(G) is called a divisor. We write D ∈ Div(G) as

\[D = \sum_{v \in V(G)} a_v \cdot (v),\]

where a^v ∈ Z. The coefficient of (v) in D is sometimes denoted D(v); that is, D(v) = av. The degree of a divisor is the sum of the coefficients:

\[\deg(D) = \sum_{v \in V(G)} D(v) = \sum_{v \in V(G)} a_v.\]

We say D is effective, written D ≥ 0, if D(v) ≥ 0 for all v.

The Laplacian matrix L of G is the |V (G)| × |V (G)| matrix whose diagonal entries record the valences of the vertices of G, and whose off-diagonal entry Lij is equal to minus the number of edges connecting vertex i to vertex j. We say that two divisors D, D′ ∈ Div(G) are equivalent, written D ∼ D′ if D − D′ (thought of as a vector) is in the Z-linear span of the columns of L. This forms an equivalence relation on Div(G).

This equivalence relation admits a more intuitive description in the language of chip-firing games. We think of a divisor D as a placement of poker chips on a graph, where vertex v has D(v) chips; note that a vertex may have a negative number of chips, in which case we describe that vertex as being "in debt." We can then perform chip-firing moves. The chip-firing move at v transforms D to D′ by removing val(v) chips from v and moving them along each edge incident to v to its neighbors. Then two divisors D and D′ are equivalent under our Laplacian definition if and only if they differ by a sequence of chip-firing moves. Three equivalent divisors are illustrated in Figure 2; the second is obtained from the first by chip-firing v1, and the third is obtained from the second by chip-firing u1.

¹Often this is called the degree of v; in this paper we reserve the word "degree" for another meaning.

Figure 2. Three equivalent divisors on the 2 × 4 slashed ladder graph: 2(u1) + (v1), 3(u1) − (v1) + (v2), and (u2) + 2(v2).

Performing the same collection of chip-firing moves in a different order does not change the resulting divisor. Thus we can think of simultaneously chip-firing a subset U ⊂ V (G); the net effect is that one chip moves along every edge connecting U to U ^C, since any two adjacent vertices both in U being fired cancel out with respect to each other. If chip-firing U does not introduce any new debt on G, then we refer to U as a legal firing move.

Given a divisor D, a natural question is: does there exist a divisor D′ with D ∼ D′ and D ≥ 0? Or in the language of chip placements, can we perform chip-firing moves to eliminate all debt in D? This question, sometimes called the Dollar Game, can be answered using q-reduced divisors and Dhar's burning algorithm.

Let q ∈ V (G). We say that a divisor D is q-reduced if the following two conditions are satisfied:

• (i) D(v) ≥ 0 for all v ∈ V (G) − q; and
• (ii) there does not exist a nonempty subset U ⊂ V (G) − q that is a legal firing move.

For each q, every divisor D is equivalent to a unique q-reduced divisor, denoted D^q [5, Proposition 3.1]; and D is equivalent to an effective divisor if and only if D^q is effective (note that it suffices to check that this holds for a single q).

Thus being able to find q-reduced divisors is incredibly important. Achieving condition (i) is always feasible; for instance, chip-firing q a large number of times will introduce enough chips into the rest of the graph to allow for the elimination of all debt away from q. From there, we use Dhar's burning algorithm [9] to find subsets of V (G) − q that can perform chip-firing moves. This algorithm works by starting a "fire" at q, and letting the fire propagate through the graph according to the following rules:

• If an edge is incident to a burning vertex, then that edge burns.
• If a vertex is incident to more than D(v) burning edges, then that vertex burns.

If the entire graph burns, then D is q-reduced. If there is an unburned set U ⊂ V (G)−q of vertices, then U is a legal firing move. Chip-fire U, and run the burning process on the new divisor. In each iteration, either the whole graph burns or there is a new subset of vertices to fire. Eventually the process terminates with the whole graph burning, at which point we have found our unique q-reduced divisor equivalent to D.

To generalize the question of whether or not D is equivalent to an effective divisor, we introduce the notion of rank. Roughly speaking, the rank of a divisor indicates how much added debt the

divisor can eliminate, regardless of where that debt is placed. More formally, we define r(D) = −1 if D is not equivalent to an effective divisor (meaning that D cannot even eliminate its own debt); and otherwise r(D) = r where r is the maximum nonnegative integer such that for any divisor E ≥ 0 of degree r, we have that D − E is equivalent to an effective divisor. The following result, called the Riemann-Roch Theorem for graphs, is one of the most famous results regarding the ranks of divisors. It is phrased in terms of the canonical divisor K = P v∈V (G) (val(v)−2)(v), and in terms of the graph's first Betti number g = |E(G)| − |V (G)| + 1.

Theorem 2.1 ([5]). If D is a divisor on a graph G, then

\[r(D) - r(K - D) = \deg(D) + 1 - g.\]

The divisorial gonality (or simply gonality) of a graph G, denoted gon(G), is the minimum degree of a divisor of positive rank. Informally, it is the smallest number of chips we can place on a graph such that no matter where −1 debt is placed, one can eliminate all debt with chip-firing moves. If a divisor D has positive rank and deg(D) = gon(G), we say that D achieves gonality.

Proving that the gonality of a graph is equal to k is quite involved. First, one needs to prove that there exists a divisor of degree k and positive rank; and more challengingly, one needs to show that every effective divisor of degree k − 1 has rank 0. The following lemma will be useful for us in the latter part of such arguments.

Lemma 2.1. Let q, v ∈ V (G) be distinct vertices, and let D be a q-reduced effective divisor such that D(v) = 0. Run one iteration of Dhar's algorithm on D from the vertex v. If the vertex q burns, then r(D) = 0.

Proof. Suppose for the sake of contradiction the algorithm does not burn the whole graph, although it does burn q. Then the unburned set of vertices U ⊂ V (G) − v gives a legal chip-firing move. However, since q is burned we have that U ⊂ V (G) − q is a legal firing move, a contradiction to D being q-reduced. Thus Dhar's algorithm burns the whole graph. It follows that D is v-reduced, and since D(v) = 0, we have that r(D) = 0.

Some graphs are more susceptible to arguments using Dhar's burning algorithm than others. Due to the number of edges along which fires can spread, complete graphs allow for detailed analysis using such methods, as illustrated in the following lemma.

Lemma 2.2 (Lemma 14 from [2]). The gonality of the complete graph Kⁿ is equal to n − 1, and is achieved only by placing n − 1 chips on a single vertex, or by placing 1 chip on n − 1 distinct vertices. Moreover, a single iteration of Dhar's burning algorithm will burn the entire graph when run on any other effective divisor of degree at most n − 1 starting from a vertex with zero chips.

Proof. First, we argue that a divisor of degree n − 1 in either of the given arrangements will be able to eliminate debt from the graph. In the first case, where n − 1 chips are placed on a single vertex, this vertex can be fired to send 1 chip to every other vertex of the graph, thus eliminating debt from wherever it was placed. In the second case, we can do the opposite: fire every vertex of the graph except for the one vertex v without a chip, eliminating debt from v.

Let D be another effective divisor of degree at most n − 1, let q be any vertex with D(q) = 0, and suppose for the sake of contradiction that the whole graph does not burn on the first iteration of Dhar's burning algorithm run on D starting from q. Then there must be u unburned vertices where 1 ≤ u ≤ n − 1. Since every vertex is adjacent to every other vertex, this means that each of the u unburned vertices will be incident to n − u burning edges, so each unburned vertex must have n−u chips (otherwise they would burn). So, we have deg(D) ≥ u(n−u). As a function of u, this expression is concave down, and therefore will achieve its minimum on the interval at one of the boundary points, in this case u = 1 or u = n−1. If u = 1 or u = n−1, we have u(n−u) = n−1; however, these values of u correspond exactly to the two arrangements discussed above! If 1 vertex doesn't burn, it has n − 1 chips on it, and thus all of the chips in the chip configuration. And if n − 1 vertices don't burn, then each vertex must have 1 chip on them. Since D was not one of these placements, we must have 2 ≤ u ≤ n − 2. Since u(n − u) is concave down, any value of u in this smaller range will result in n(n − u) > n − 1, contradicting deg(D) = n − 1 since deg(D) ≥ n(n − u). This completes the proof.

We say that an effective divisor D is multiplicity-free if D(v) ≤ 1 for every vertex v. In other words, D is multiplicity-free if it places 0 or 1 chips on each vertex. The multiplicity-free gonality mfgon(G) of a graph G is the minimum degree of a multiplicity-free divisor of positive rank.

We immediately have that gon(G) ≤ mfgon(G). Not every graph has gon(G) = mfgon(G); for instance, a graph G with V (G) = {v1, v2, v3} and edge multiset {v1v2, v1v2, v2v3, v2v3} has gonality 2, but every rank 1 divisor of degree 2 is of the form 2(vi) for some i. It turns out there are also simple graphs with a gap between the two versions of gonality, as shown in the following examples.

Example 2.1. Consider the graph G on 8 vertices illustrated in Figure 1. We refer to this as the 2 × 4 slashed ladder graph. If we construct a divisor D by placing 3 (or fewer) chips on distinct vertices, there exists some i such that uⁱ and vⁱ both lack chips. We claim that running Dhar's burning algorithm on D starting fro uⁱ then burns the whole graph. Certainly vⁱ also burns, and then any neighboring u^j , v^j pair will burn as well: even if each has a chip, one has 2 incident burning edges and burns, and then the other has 2 incident burning edges and burns. This propagates until the whole graph burns, implying that r(D) = 0. However, there does exists a divisor of positive rank and degree 3, namely D = 2(u1) + (v1); this divisor appears in Figure 2. This is equivalent to the divisors (u2) + 2(v2), 2(u3) + (v3), and (u4) + 2(v4); since together they cover all vertices of G, we have r(D) > 0. Some quick case-checking verifies that gon(G) > 2, so G is a graph of gonality 3 such that no multiplicity-free divisor achieves gonality. Indeed, generalizing to the 2 × m slashed ladder graph, we can find examples of graphs with gonality 3 and multiplicity-free gonality at least (and in fact equal to) m.

There also exist regular simple graphs with a gap between gonality and multiplicity-free gonality.

Example 2.2. The antiprisms are 4-regular graphs that give us a gap between gonality and multiplicity-free gonality. Consider the antiprism A¹¹ on 2 · 11 = 22 vertices pictured in Figure 3. This graph has vertices u1, . . . , u¹¹ and v1, . . . , v¹¹ arranged in two 11-cycles, with uⁱ attached to

Figure 3. The antiprism on 11 vertices, and a degree 10 divisor achieving gonality.

\(v_i\) and \(v_{i+1}\), working modulo 11. The divisor \(3(u_1) + (u_2) + (u_3) + (v_1) + (v_2) + 3(v_3)\) pictured has positive rank, as can be checked using Dhar's burning algorithm, implying that \(gon(\mathfrak{A}_{11}) \leq 10\).

We claim that no multiplicity-free divisor on \(\mathfrak{A}_{11}\) has degree 10 or less, implying \(\operatorname{gon}(G) < \operatorname{mfgon}(G)\). Let D be an effective multiplicity-free divisor on \(\mathfrak{A}_{11}\) of degree 10. Since there are 11 \(\{u_i,v_i\}\) pairs, at least one such pair has no chips on it. Choose such a pair, and run Dhar's burning algorithm on D starting from \(u_i\). Certainly \(v_i\) will burn as well. Letting \(j=i\pm 1\), we claim that \(u_j\) and \(v_j\) now burn as well. Indeed, one of them has two burning edges coming from the pair \(\{u_i,v_i\}\), so it will burn; and then the other has one burning edge from \(\{u_i,v_i\}\) and one from the other element of \(\{u_j,v_j\}\). Thus the fire spreads through the whole graph, implying that r(D)=0. Thus \(\mathfrak{A}_{11}\) is a 4-regular graph such that no multiplicity-free divisor on it achieves gonality.

For a 5-regular graph, we can add more edges to the antiprism. In addition to connecting \(u_i\) to \(v_i\) and \(v_{i+1}\), connect \(u_i\) to \(v_{i-1}\) (again working cyclically). Building such a graph G on \(2 \cdot 9 = 18\) vertices, we see that \(gon(G) \leq 8\), since the divisor illustrated in Figure 4 has positive rank. However, an argument identical to that for the antiprism shows that any multiplicity-free divisor of degree 8 or less has rank 0. Thus this is a 5-regular graph with multiplicity-free gonality strictly larger than gonality. We will see in Proposition 5.2 that for any \(r \geq 4\), there exist simple (and non-simple) r-regular graphs with a gap between gonality and multiplicity-free gonality.

We now present several useful lemmas on multiplicity-free gonality.

Lemma 2.3. Let G be a graph on n vertices such that every pair of adjacent vertices share at least 2 edges. Then mfgon(G) = n.

Proof. Let D be a multiplicity-free divisor on G with \(\deg(D) < n\). At least one vertex \(v \in V(G)\) has no chip from D. Run Dhar's burning algorithm on D starting from v. Anytime a vertex burns, all of its neighbors will burn, since they will have at least two incident burning edges, and each vertex has at most 1 chip on it. Since G is connected, the whole graph will burn. It follows that

Figure 4. A 5-regular graph with a positive rank divisor of degree 8.

r(D) = 0, implying that mfgon(G) ≥ n. Since placing 1 chip on every vertex gives a positive rank divisor, we have mfgon(G) ≤ n, completing the proof.

A set S ⊂ V (G) is called an independent set if no two vertices of S share an edge. The independence number of G, denoted α(G), is the maximum possible size of an independent set.

Lemma 2.4. If G is a simple graph, then mfgon(G) ≤ n − α(G).

Proof. Let S be an independent set with |S| = α(G), and consider the multiplicity-free divisor D with D(v) = 0 for v ∈ S and D(v) = 1 for v /∈ S. As proved in [8, Proposition 3.1], this divisor has positive rank; to see this, note that for v ∈ S, chip-firing the set {v} ^C moves chips onto v without introducing new debt, since each neighbor of v has 1 chip and is connected to v by exactly one edge. Since D is multiplicity-free, we have mfgon(G) ≤ deg(D) = n − α(G).

We close this section by remarking on a possible generalization of multiplicity-free gonality, leaving it as a direction for future research. Just as the gonality of a graph G can be defined as the minimum degree of a divisor with rank at least 1, for any positive integer r we can define the r th gonality of a graph G to be the minimum degree of a divisor with rank at least r. This number is denoted gon^r (G).

It is natural to try to define mfgon^r (G) as the minimum degree of a multiplicity-free divisor with rank at least r; however, this number is not always well-defined. This is because there are only finitely many multiplicity-free divisors on a graph, and thus the maximum rank of such a divisor is bounded. Thus we define mfgon^r (G) as the minimum degree of a multiplicity-free divisor with rank at least r if such a divisor exists, and ∞ otherwise. A natural question then becomes:

Question. Given a graph G, for what values r do we have mfgon^r (G) < ∞?

Note that the maximum rank of a multiplicity-free divisor is achieved by the divisor D¹ that places 1 chip on every vertex. Thus, mfgon^r (G) < ∞ if and only if r ≤ r(D1). So really, the question is: given a graph G, what is r(D1)?

We answer this question in a few cases. Recall that g = |E(G)| − |V (G)| + 1 is the first Betti number of the graph.

• If G is a tree, then r(D1) = deg(D1) = |V (G)|; and if G is a cycle, then r(D1) = deg(D1)− 1 = |V (G)| − 1. This is because for a graph with g = 0 (i.e. a tree), the rank of a divisor is equal to its degree; and for a graph with g = 1, the rank of an effective divisor of positive degree is one less than its degree (both results follow from Theorem 2.1).
• If G is a simple graph, we have r(D1) ≥ 2: the only non-effective divisor of the form D¹ − E where E ≥ 0 and deg(E) = 2 is D¹ − 2(v) for some vertex v; this divisor can be made effective by chip-firing all vertices but v. On the flip side, if G is a multigraph where every pair of adjacent vertices are connected by 2 or more edges, then r(D1) = 1; this is because running Dhar's burning algorithm on D¹ − (v) starting from v burns the whole graph, implying that debt cannot be eliminated in D¹ − 2(v) (the proof is similar to that of Lemma 2.3). Thus any simple graph has mfgon² (G) ≤ |V (G)|, while any graph with all edges multiedges has mfgon² (G) = ∞.
• If G is a 3-regular graph, then D¹ is K, the canonical divisor on G from the Riemann-Roch Theorem for graphs. By that theorem, we know that r(K) = g − 1. Thus for any 3-regular graph we have mfgon^r (G) < ∞ if and only if r ≤ g − 1.
• More generally, if G is a k-regular graph, then D¹ is a divisor D such that (k − 2)D = K. Note that g −1 = r(K) = r((k −2)D) ≥ (k −2)r(D), so we have r(D) ≤ (g −1)/(k −2). However, for k > 3, r(D1) need not be determined by g. Consider the two 4-regular graphs with g = 7 in Figure 5. As previously argued, the simple graph has r(D1) ≥ 2, while the graph with all edges multiedges has r(D1) = 1.

Figure 5. Two 4-regular graphs with g = 7 with different values for the rank of D1.

A more thorough study of this question would be an interesting direction for future work.

3. A condition for equality

In this section we provide a sufficient condition for a graph to have gonality equal to multiplicityfree gonality. We start with the following lemma.

Lemma 3.1. Let G be a k-connected simple graph, and let U ⊂ V (G) be a set of vertices with 2 ≤ |U| ≤ k − 1. Then the outdegree of U is at least k + 1.

Proof. The outdegree of U can be computed as the total valence of the vertices in U, minus twice the number e of edges between vertices of U due to double-counting; thus the outdegree is

\[\operatorname{outdeg}(U) = \sum_{v \in U} \operatorname{val}(v) - 2e.\]

As G is a k-connected graph, any vertex in G must be incident to at least k edges, since the set of neighbors of a vertex forms a vertex cut. Thus P v∈U val(v) ≥ k|U|. On the other hand, since G is simple, the total number of edges in U is at most |U| 2 = |U|(|U|−1) 2 . Thus we have

outdeg\[(U) \ge k|U| - |U|(|U| - 1)\].

To show that k|U| − |U|(|U| − 1) is at least k + 1, it is equivalent to show that

\[k \cdot (|U| - 1) - |U| \cdot (|U| - 1) \ge 1\]

since we can subtract k from both sides. Factoring transforms this expression into the following:

\[(k - |U|)(|U| - 1) \ge 1.\]

Since k > |U| and |U| > 1, both k − |U| and |U| − 1 are positive integers, so this inequality holds for all values of k and |U|. This completes the proof.

Now that we have this lemma, we can prove the following proposition:

Proposition 3.1. For any simple graph G, if gon(G) = κ(G) = k, then gon(G) = mfgon(G).

Proof. If κ(G) = gon(G) = 1, then G is a tree and we are done. Henceforth we assume that κ(G) ≥ 2. Since gon(G) = κ(G) = k, there exists an effective divisor D of degree k and positive rank.

Let S be the set of vertices on which D places chips, and let ℓ = |S|. Suppose for the sake of contradiction that 2 ≤ ℓ ≤ k − 1. Let q be a vertex with no chip, and run Dhar's burning algorithm on D starting from q. Since κ(G) = k, removing the ℓ ≤ k − 1 vertices of S won't disconnect the graph, so every vertex not in S will burn. Since r(D) > 0, the burning process stops before the entire set S burns. Call the set of unburned vertices U. If |U| = 1, then the single unburned would need k chips on it, contradicting the condition that |S| ≥ 2, since U ⊆ S. Thus we have 2 ≤ |U| ≤ k − 1. But by Lemma 3.1, U has outdegree at least k + 1, so it requires at least k + 1 chips for no vertices in it to burn, a contradiction to deg(D) = k.

Thus ℓ = 1 or ℓ = k. If ℓ = k, then D is multiplicity-free and we are done. If ℓ = 1, then D places all chips on a single vertex v. Since κ(G) ≥ 2, we know that G−v is connected. Choose any vertex w ̸= v, and run Dhar's burning algorithm on D starting from w. The whole graph besides v will burn, since G − v is connected; but v will not burn since r(D) > 0. Thus it is possible to chip-fire v by itself without introducing debt. This means v is adjacent to at most k vertices; but since κ(G) = k, it is also adjacent to at least k vertices, so it must be adjacent to exactly k vertices. Thus chip-firing v turns D into a multiplicity-free divisor, with one chip on each of the k neighbors of v. Either way, there exists a multiplicity-free divisor on G achieving gonality.

There are many familiar families of graphs to which Proposition 3.1 applies, including:

• trees, which have κ(G) = gon(G) = 1 [6, Lemma 1.1] (indeed, that lemma proves that the trees are the only graphs of gonality 1);
• complete multipartite graphs Kⁿ1,...,n^ℓ , which have κ(G) = gon(G) = P^{ℓ i}=1 nⁱ −maxⁱ nⁱ [14, Example 4.3];
• cycle graphs, which have κ(G) = gon(G) = 2 [13, §4.2].

In fact, the last example falls into a more general class of graphs with gonality equal to multiplicity-free gonality:

Proposition 3.2. If G is a simple graph, then gon(G) = 2 if and only if mfgon(G) = 2.

Proof. If mfgon(G) = 2, then G is not a tree, so 1 < gon(G) ≤ mfgon(G) = 2. It follows that gon(G) = 2.

Now let G be simple with gon(G) = 2, and let D = (u) + (v) be an effective divisor with deg(D) = 2 and r(D) = 1. If u ̸= v, then D is multiplicity-free, and we are done. If u = v, choose any vertex q ̸= u and run one iteration of Dhar's burning algorithm on D starting from q. Since r(D) ≥ 1, the whole graph will not burn, and so a subset U of chips will be made to fire. Let D′ be the divisor obtained by performing this subset-firing move. At least one chip moved from u, and even if both chips moved they could not have moved to the same vertex, since the graph is simple. Thus D′ is a multiplicity-free divisor of rank 1 and degree 2, implying that mfgon(G) = 2.

We will see in the next section that Proposition 3.2 no longer holds if we drop the assumption that G is simple.

4. Multiplicity-free gonality cannot be bounded by gonality

We have that gon(G) = 1 if and only if mfgon(G) = 1 if and only if G is a tree; and for simple graphs that gon(G) = 2 if and only if mfgon(G) = 2 by Proposition 3.2. In this section we will prove that these are the only cases in which gonality determines multiplicity-free gonality, or even in which some function of gonality can bound multiplicity-free gonality.

Proposition 4.1. If 2 ≤ i ≤ j, then there exists a multigraph with gon(G) = i and mfgon(G) = j.

Proof. Consider the multipath on j vertices, with i edges between each pair of adjacent vertices. By [1, §5], we have gon(G) = min(i, j) = i; and by Lemma 2.3, we have mfgon(G) = j.

The corresponding result for simple graphs will take more work to prove.

Theorem 4.1. For any integers i, j, with 3 ≤ i ≤ j, there exists a simple graph G with gon(G) = i and mfgon(G) = j.

Figure 6. The complete slashed ladder KL6,5.

In order to prove this theorem, we introduce the complete slashed ladder graph, KLm,n, obtained by attaching a complete graph on n vertices to the end of a 2 × m slashed ladder graph, overlapping on 2 vertices (throughout this section we assume m ≥ 2 and n ≥ 3). The complete slashed ladder KL6,⁵ is illustrated in Figure 6.

Lemma 4.1. For all m ≥ 2 and n ≥ 3, the complete slashed ladder graph KLm,n has gonality n.

Proof. First we present a positive rank divisor of degree n. This divisor places 3 chips on the first column of the slashed ladder graph, with 2 chips on the vertex incident to the diagonal edge and 1 chip on the other vertex, and adds 1 chip to all but one of the remaining n − 2 vertices of the complete portion of the graph. This divisor is shown in Figure 7 for KL6,5.

Figure 7. Divisor of degree 5 for KL6,5.

This divisor has positive rank, because if debt is introduced on the slashed ladder portion of the graph, we can use the slashed ladder graph strategy to eliminate it; namely, chip-fire the entire complete graph portion of KLm,n to move the 3 chips over to the second column of the slashed ladder graph, then chip-fire larger and larger subsets until the chips have eliminated the debt on the slashed ladder graph. If debt is instead introduced on the last remaining vertex of the complete portion of the graph, chip-firing every single other vertex will eliminate debt from the graph. So, gon(KLm,n) ≤ n.

Suppose for the sake of contradiction that there is a positive rank effective divisor D of degree n − 1. Of the two vertices in the overlap of the complete graph and the slashed ladder, choose q to be the one with higher valence. Without loss of generality we may assume that D is q-reduced, so there is at least 1 chip on q. To reach a contradiction at this point, it suffices by Lemma 2.1 to find

a vertex v ∈ V (G) with D(v) = 0 such that running Dhar's burning algorithm on D starting from v burns the vertex q.

Since there are only n − 1 chips, there must be at least one vertex v in the Kⁿ portion of the graph with no chips on it. Run Dhar's burning algorithm on D starting from v. We know by Lemma 2.2 that for the Kⁿ subgraph (including q) not to burn with at most n − 1 chips on it, it must have all n − 1 chips, and either they must all be at q, or 1 chip must be on each vertex of the Kⁿ except for v. Based on this information regarding the structure of D, we may now change our choice of v.

If D has all n − 1 chips on q, as in Figure 8, then any choice of v immediately burns the connected subgraph G − q, and then q as well since it is adjacent to more than n − 1 vertices.

Figure 8. Degree 4 divisor on KL6,⁵ where all 4 chips are on q, with −1 chips on a different vertex.

If, instead, D has 1 chip on every vertex of Kⁿ except for one, as in Figure 9, then choose v to be in the complete slashed ladder portion of the graph. Running Dhar's burning algorithm from v burns the whole slashed ladder away from Kn, and then q burns as well since it has one chip and is incident to two burning edges, again giving us a contradiction.

Figure 9. Degree 4 divisor on KL6,⁵ where each vertex has 1 chip, with −1 chips on a vertex of the slashed ladder.

Thus, it is impossible for a degree n − 1 divisor to have positive rank. We conclude that the complete slashed ladder graph KLm,n has gonality n.

Lemma 4.2. For all m ≥ 2 and n ≥ 3, the complete slashed ladder graph KLm,n has multiplicityfree gonality n + m − 2.

Proof. One multiplicity-free divisor of degree n + m − 2 that has positive rank is the one that places a chip on each of the m vertices along the diagonal of the slashed ladder portion of the graph, plus a chip on each of the n − 2 vertices of the Kⁿ portion of the graph that aren't part of the slashed ladder. Indeed, this is a placement of chips on the complement of an independent set, which always has positive rank for a simple graph [8, Proposition 3.1]. This divisor can be seen on KL6,⁵ in Figure 10.

Figure 10. Degree 9 multiplicity-free divisor on KL6,5.

Now let D be an arbitrary multiplicity-free divisor. We claim that if a column of the slashed ladder graph portion has no chips on it from D, then there exists a choice of vertex v such that the whole graph burns when running Dhar's burning algorithm on D starting from v. This can be seen as follows: if a column has no chips, we can start a fire on one of the vertices in that column. Then, the other vertex in the column will burn, as well as all incident edges to each vertex in the column. Because of the structure of the slashed ladder graph, there will be a vertex in each adjacent column that now has two burning edges incident to it, and at most 1 chip on it, so it will burn, and then the other vertex in its column will burn as well for the same reason. This process continues until the entire slashed ladder is burning. Once the entire slashed ladder burns, the complete graph will already have 2 burning vertices, and thus no vertex with at most 1 chip on it will avoid burning. So, for D to have positive rank, it must place at least m chips on the complete slashed ladder portion of the graph (at least one on each column).

Similarly, if the Kⁿ portion of the complete slashed ladder graph burns, then the entire graph will burn, because the Kⁿ portion contains a complete column of the slashed ladder graph within it. Thus, if Kⁿ burns, the slashed ladder will burn as well, and therefore the whole graph will burn. We know by Lemma 2.2 that there must be n − 1 chips on Kⁿ to prevent it from burning, and the chips must be placed on all but 1 vertex of Kn. Thus there is a chip on at least n − 1 of the vertices of the complete graph, and at least one chip on each of the m columns of the slashed ladder graph. This means there are at least m+n−2 chips in total, where the savings of 1 comes from the ability to have one of the columns of the slashed ladder taken care of by the complete graph's chips. We conclude that the multiplicity-free gonality of the complete slashed ladder graph is at least, and therefore exactly, m + n − 2.

We are now ready to prove Theorem 4.1.

Proof of Theorem 4.1. For \(3 \le i \le j\), let n = i and m = j - n + 2. Then, the complete slashed ladder graph \(KL_{m,n}\) has gonality i and multiplicity-free gonality j, for any desired values of i and j.

5. Families of graphs

We close our paper by studying the mutiplicity-free gonality of graphs for certain graph families, or graphs with a particular structure. In some cases we compute multiplicity-free gonalities where gonalities are unknown, and in other cases we can compare the two types of gonality.

5.1. ℓ-dimensional rook's graphs

The Cartesian product \(G \square H\) of two simple graphs G and H is the graph \(G \square H\) whose vertex set is \(V(G) \times V(H)\), where \((u_1, v_1)\) is adjacent to \((u_2, v_2)\) if and only if either \(u_1 = u_2\) and \(v_1\) is adjacent to \(v_2\) in H, or \(v_1 = v_2\) and \(u_1\) is adjacent to \(u_2\) in G. An \(\ell\)-dimensional rook's graph is a Cartesian product of \(\ell\) complete graphs. For n = 2, it was shown that \(gon(K_m \square K_n) = min\{m(n-1), n(m-1)\}\) for \(min\{m, n\} \leq 5\) in [2]. This was extended to all m and n in [12], where it was also shown that \(gon(K_2 \square K_m \square K_n) = mn\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq m\) for \(1 \leq\)

Proposition 5.1. Let \(n_1 \leq \cdots \leq n_\ell\), and consider \(G = K_{n_1} \square \ldots \square K_{n_\ell}\). We have

\[mfgon(G) = (n_1 - 1)n_2 \dots n_{\ell}.\]

Proof. To see that \(\operatorname{mfgon}(G) \leq (n_1 - 1)n_2 \cdots n_\ell\), we consider the following multiplicity-free divisor of this degree: we may view G as \(n_1\) copies of \(K_{n_2} \square \cdots \square K_{n_\ell}\), connected according to \(K_{n_1}\). Choose one copy \(H = K_{n_2} \square \cdots \square K_{n_\ell}\) inside G, and place a chip on every vertex in \(V(G) \setminus V(H)\). This divisor is multiplicity-free of degree \((n_1 - 1)n_2 \cdots n_\ell\) and has positive rank, as we may fire all vertices outside of H to eliminate debt wherever it is placed on H.

We will now prove by induction on \(\ell\) that if D is a multiplicity-free divisor of degree \((n_1-1)n_2\cdots n_\ell-1\) on \(K_{n_1} \square \cdots \square K_{n_\ell}\), then there exists a vertex v on the graph with D(v)=0 such that the entire graph burns on one iteration of Dhar's burning algorithm on D starting from v. It will follow that no such multiplicity-free divisor has positive rank, giving us the desired lower bound on multiplicity-free gonality.

For the base case of \(\ell=1\), our claim amounts to saying that if \(K_n\) has an effective divisor D of degree (n-1)-1=n-2, then there exists \(v\in V(K_n)\) such that the whole graph burns on one iteration of Dhar's burning algorithm run on D starting from v. This follows from Lemma 2.2.

Now let \(\ell \geq 2\), and assume our claim holds for \((\ell-1)\)-fold products of complete graphs. Let D be an effective multiplicity-free divisor of degree \((n_1-1)n_2\cdots n_\ell-1\) on \(G=K_{n_1}\square\cdots\square K_{n_\ell}\). We can view G as \(n_\ell\) copies of \(K_{n_1}\square\cdots\square K_{n_{\ell-1}}\), with matching vertices connected according to \(K_{n_\ell}\). Refer to these copies as \(H_1,\cdots,H_{n_\ell}\). At least one \(H_i\) has at most \((n_1-1)n_2\cdots n_{\ell-1}-1\) chips on it: otherwise the degree of D would be at least \((n_1-1)n_2\cdots n_\ell\). By our inductive hypothesis, there exists a vertex \(v\in V(H_i)\) such that all of \(H_i\) burns under one iteration of Dhar's burning algorithm. There exists some other index j such that \(H_j\) has at most \(n_1n_2\cdots n_{\ell-1}-1\) chips: otherwise the degree of D would be at least \(n_1n_2\cdots n_{\ell-1}(n_\ell-1)\geq (n_1-1)n_2\cdots n_{\ell-1}n_\ell\). So at least one vertex

in \(H_j\), say w, does not have a chip. Every vertex in \(H_j\) is adjacent to a vertex in \(H_i\), and so is incident to a burning edge. This means the vertex w burns. From there every vertex in \(H_j\) adjacent to w will burn; then every vertex in \(H_j\) adjacent to those vertices will burn; and so on. Since \(H_j\) is connected, every vertex in \(H_j\) will burn. Every other vertex w in w is adjacent to a vertex in w and to a vertex in w is incident to two burning edges, and w will burn as well. Thus the whole graph w burns.

Since no multiplicity-free divisor of degree \((n_1 - 1)n_2 \cdots n_\ell - 1\) has positive rank, we have \(\operatorname{mfgon}(G) \geq (n_1 - 1)n_2 \cdots n_\ell\). We conclude that \(\operatorname{mfgon}(G) = (n_1 - 1)n_2 \cdots n_\ell\).

5.2. Wheel graphs

The wheel graph \(W_n\) on n+1 vertices consists of a cycle on n vertices (referred to as radial vertices) together with a universal vertex. To determine which wheel graphs have multiplicity-free gonality equal to gonality, we must first determine the gonality of \(W_n\).

Theorem 5.1. For all \[n \geq 3\], we have \(gon(W_n) = \lceil \sqrt{n} \rceil - 1 + \lceil \frac{n}{\lceil \sqrt{n} \rceil} \rceil\)

Proof. Let D be an effective divisor achieving gonality on \(W_n\), and suppose for the sake of contradiction that \(\deg(D) \leq \lceil \sqrt{n} \rceil - 2 + \left\lceil \frac{n}{\lceil \sqrt{n} \rceil} \right\rceil\). Let w be the universal vertex. Without loss of generality, we will assume that D is w-reduced.

Let k=D(w); we know that \(k\geq 1\), since D is w-reduced and r(D)=1. We claim that there exist k+1 radial vertices \(v_1,\ldots,v_{k+1}\) forming a path such that \(D(v_i)=0\) for all i. Suppose not. This means that there are at least \(\lceil \frac{n}{k+1} \rceil\) chips placed on the radial vertices; otherwise the prescribed gap would exist. It follows that \(k\leq \deg(D)-\lceil \frac{n}{k+1}\rceil \leq \lceil \sqrt{n}\rceil-2+\lceil \frac{n}{\lceil \sqrt{n}\rceil}\rceil-\lceil \frac{n}{k+1}\rceil\). This can be rewritten as

\[(k+1) + \left\lceil \frac{n}{k+1} \right\rceil + 1 \le \lceil \sqrt{n} \rceil + \left\lceil \frac{n}{\lceil \sqrt{n} \rceil} \right\rceil\]

Note that \((k+1)+\lceil\frac{n}{k+1}\rceil+1=\lceil(k+1)+\frac{n}{k+1}+1\rceil\). Consider the function \(x+\frac{n}{x}+1\). This function is concave up for all positive x, and is minimized at \(x=\sqrt{n}\). If k can be any positive integer, it follows that \((k+1)+\frac{n}{k+1}+1\) is at its minimum when k+1 is either \(\lfloor \sqrt{n} \rfloor\) or \(\lceil \sqrt{n} \rceil\); the same is true for \(\lceil (k+1)+\frac{n}{k+1}+1 \rceil\). In fact, by Proposition Appendix A.1, these two choices for k+1 give the same output. It follows that

\[\lceil \sqrt{n} \rceil + \left\lceil \frac{n}{\lceil \sqrt{n} \rceil} \right\rceil + 1 \le (k+1) + \left\lceil \frac{n}{k+1} \right\rceil + 1 \le \lceil \sqrt{n} \rceil + \left\lceil \frac{n}{\lceil \sqrt{n} \rceil} \right\rceil,\]

a contradiction. This lets us conclude that there exist \(v_1, \ldots, v_{k+1}\) as claimed.

Run Dhar's burning algorithm on D starting from \(v_1\). The vertices \(v_1,\ldots,v_{k+1}\) all burn, since they are connected and \(D(v_i)=0\) for all i. The vertex w is now incident to k+1 burning edges, and so will burn as well since D(w)=k. If the graph does not burn, then some subset of \(V(W_n)\) not including w can fire, contradicting the fact that D is w-reduced. Thus the whole graph will burn and r(D)<1, a contradiction. We conclude that the gonality of \(W_n\) is at least \(\lceil \sqrt{n} \rceil-1+ \lceil \frac{n}{\lceil \sqrt{n} \rceil} \rceil\).

To see that the gonality of \(W_n\) is at most \(\lceil \sqrt{n} \rceil - 1 + \left\lceil \frac{n}{\lceil \sqrt{n} \rceil} \right\rceil\), place \(\lceil \sqrt{n} \rceil - 1\) chips on w, and place \(\left\lceil \frac{n}{\lceil \sqrt{n} \rceil} \right\rceil\) chips around the radial vertices so that no two chipped vertices in a row are more than \(\lceil \sqrt{n} \rceil\) apart on the outer cycle. This is illustrated for n=12 on the wheel with 13 vertices in Figure 11. The only vertices without chips are then radial vertices in clusters of length at most \(\lceil \sqrt{n} \rceil - 1\). If -1 is placed on such a vertex, then firing all vertices not in its cluster eliminates all debt from the graph. Thus, there exists a positive rank divisor of degree \(\lceil \sqrt{n} \rceil - 1 + \left\lceil \frac{n}{\lceil \sqrt{n} \rceil} \right\rceil\).

Figure 11. A winning placement of chips on the wheel with 13 vertices

Now we determine the multiplicity-free gonality of \(W_n\). We will use the following lemma.

Lemma 5.1. Let G be a simple graph with a universal vertex v such that G - v is connected. Then \(mfgon(G) = n - \alpha(G)\).

Proof. We have \(\operatorname{mfgon}(G) \leq n - \alpha(G)\) by Lemma 2.4. Now let D be a multiplicity-free divisor of degree less than \(n - \alpha(G)\). It follows that D that has two adjacent vertices u and w that do not have chips. Run Dhar's burning algorithm starting from either of these vertices, so that both u and w burn. Either \(v \in \{u, w\}\), in which case both v and a vertex of G - v burn; or \(v \notin \{u, w\}\), in which case v has two burning edges and at most 1 chip and thus we still have both v and a vertex of G - v burn. At this point every vertex in G - v has at least one burning edge coming from v, meaning that one more burning edge is enough to make them burn; and since G - v is connected with at least one burning vertex, the fire spreads through the whole graph. Thus v(D) = 0, and so there does not exist a multiplicity-free divisor of degree less than v(C) = 0 of positive rank. This gives us v(C) = v(C), completing the proof.

Corollary 5.1. For all \(n \geq 3\), we have \(mfgon(W_n) = \lceil n/2 \rceil + 1\).

Proof. This follows from Lemma 5.1, the fact that \(\alpha(W_n) = \lfloor n/2 \rfloor\), and the identity \((n+1) - \lfloor n/2 \rfloor = \lceil n/2 \rceil + 1\).

Theorem 5.2. The wheel \(W_n\) has gonality equal to multiplicity-free gonality if and only if \(n \le 8\) or n = 10.

We reserve the proof of this result for Proposition Appendix A.2 in Appendix Appendix A; it is simply a verification that these are the only values of n that make the formulas from Theorem 5.1 and Corollary 5.1 equal to one another. The small wheel graphs that do have gonality achieved by a multiplicity-free divisor are pictured in Figure 12, along with such a divisor.

Figure 12. Wheel graphs with multiplicity-free divisors achieving gonality.

5.3. Simple graphs with high minimum valence

In [10], it was shown that if a simple graph G on n vertices has minimum valence δ(G) ≥ ⌊n/2⌋ + 1, then

\[gon(G) = n - \alpha(G).\]

Since gon(G) ≤ mfgon(G) ≤ n − α(G), we immediately have the following result:

Corollary 5.2. Let G be a simple graph on n vertices with minimum valence δ(G) ≥ ⌊n/2⌋ + 1. Then gon(G) = mfgon(G) = n − α(G).

The authors of [10] leveraged their result to provide a new proof that it is NP-hard to compute the gonality of a simple graph, a result originally proved in [11]. We can mirror their argument to do the same for multiplicity-free gonality.

Theorem 5.3. Computing mfgon(G) is NP-hard.

Proof. Let H be any simple connected graph on m vertices, and let G be the mth cone over H. That is, G is obtained from H by iteratively adding m universal vertices to it. Letting n = 2m, we have that G is a graph on n vertices with δ(G) ≥ n/2 + 1, implying by Corollary 5.2 that mfgon(G) = n − α(G). Noting that α(H) = α(G), we have mfgon(G) = n − α(H). This means we may compute the independence number of any simple graph H by computing the multiplicity free gonality of a graph G that is polynomial in the size of H. Since independence number is NP-hard to compute, we conclude that mfgon(G) is NP-hard to compute as well.

5.4. Regular graphs

In this subsection we consider the question: for which values of r do there exist r-regular graphs with a gap between gonality and multiplicity-free gonality? We remark that the only connected 1 regular graph is K2, which has gonality and multiplicity-free gonality equal to 1; and the only connected 2-regular graphs are the cycle graphs Cn, which have gonality and multiplicity-free gonality both equal to 2. Once we have r ≥ 4, however, we can find graphs exhibiting a gap between the two gonalities, both among simple graphs and multigraphs.

Proposition 5.2. For any \(r \geq 4\), there exist simple and non-simple r-regular graphs G with gon(G) < mfgon(G).

Proof. The non-simple graph is easier, so we construct that one first. We illustrate our constructed graphs for r=4 and r=5 in Figure 13. If r is even, construct a multigraph G on r+1 vertices with the cycle \(C_{r+1}\) as the underlying simple graph, where each adjacent pair of vertices is connected by r/2 edges; this makes G an r-regular graph. Then for any \(v \in V(G)\), the divisor r(v) has nonnegative rank: it is equivalent to \(\frac{r}{2}(v') + \frac{r}{2}(v'')\) for any pair of vertices \(v' \neq v''\) equidistant from v on the cycle. Thus \(gon(G) \leq r < r+1 = |V(G)|\). Since there are \(r/2 \geq 2\) edges between each pair of neighboring vertices, we may apply Lemma 2.3 to conclude that G has gonality strictly smaller than multiplicity-free gonality.

If r is odd, write r=2s+1. Construct G on 2s(s+1)+2 vertices with the cycle \(C_{2s(s+1)+2}\) as the underlying graph, where the number of edges between two vertices alternates between s and s+1 as we move around the cycle. Thus the degree of each vertex is s+s+1=2s+1=r, making G an r-regular graph, Choose two vertices \(v_1\) and \(v_2\) connected by s edges, and consider the divisor \(D=s(s+1)(v_1)+s(s+1)(v_2)\). By chip-firing the set \(\{v_1,v_2\}\) a total of s times, we have that D is equivalent to \(s(s+1)(w_1)+s(s+1)(w_2)\), where \(w_i\) is the neighbor of \(v_i\) not in \(\{v_1,v_2\}\). Then, by chip-firing the set \(\{v_1,v_2,w_1,w_2\}\) a total of s+1 times, we have that D is equivalent to \(s(s+1)(u_1)+s(s+1)(u_2)\), where \(u_i\) is the neighbor of \(w_i\) not in \(\{v_1,v_2\}\). Continuing in this way, we may move our chips around the whole graph, so r(D)>0. This means that \(gon(G) \leq deg(D) = 2s(s+1) < 2s(s+1) + 2 = |V(G)|\). Since \(r \geq 5\), there are at least \(s \geq 2\) edges between each pair of neighboring vertices, so we may apply Lemma 2.3 to conclude that G has gon(G) < mfgon(G).

Figure 13. The 4-regular and 5-regular non-simple graphs constructed in the proof, along with positive rank divisors.

We now construct a simple graph with our desired properties. The graph we will end up constructing for r = 7 appears in Figure 14; there are 9 copies of \(K_4\), connected as pictured.

If r=4 or r=5, we can use one of the graphs from Example 2.2. Now let \(r\geq 6\). Choose N such that \(\frac{4(r-3)}{r-4}< N\), and construct N copies of \(K_{r-3}\), referring to them as \(K_{r-3}^{(1)},\cdots,K_{r-3}^{(N)}\). Label the vertices of \(K_{r-3}^{(i)}\) as \(v_1^{(i)},\cdots,v_{r-3}^{(i)}\). Let \(\overline{n}\) denote \(n \mod N\). For pairs \(i_1\) and \(i_2\) with \(i_2=\overline{i_1+1}\), connect \(v_j^{(i_1)}\) to both \(v_j^{(i_2)}\) and \(v_{\overline{j+1}}^{(i_2)}\) for all j. (Without the \(v_j^{(i_1)}v_{\overline{j+1}}^{(i_2)}\) edges, this graph

Figure 14. A simple 7-regular graph with gon(G) < mfgon(G); there are 9 copies of \(K_4\).

would simply be the Cartesian product \(K_{r-3} \square C_N\), which is a regular graph with all degrees equal to r-4+2=r-2. The additional edges increase this to r, making G an r-regular graph.)

Note that every vertex v in G has valence (r-4)+4=r, where r-4 edges come from the \(K_{r-3}\) containing v and the other 4 edges connect v to other copies of \(K_{r-3}\). Also note that \(gon(G) \leq 4(r-3)\): placing 4 chips on every vertex of one copy of \(K_{r-3}\) yields a positive rank divisor, as we may spread these chips around the graph by iteratively firing copies of \(K_{r-3}\). Suppose G has a multiplicity-free divisor D achieving gonality. Then \(deg(D) \leq 4(r-3)\). Since we chose N such that \(\frac{4(r-3)}{r-4} < N\), we have \(\frac{4(r-3)}{N} < r-4\), so \(\left\lfloor \frac{4(r-3)}{N} \right\rfloor \leq r-5\), and thus by the Pigeonhole Principle at least one copy of \(K_{r-3}\) has at most r-5 chips on it. Choose a vertex q of this \(K_{r-3}\) with no chips on it, and run Dhar's burning algorithm on D starting from q. By Lemma 2.2, the copy of \(K_{r-3}\) containing q burns. Then, the two neighboring copies of \(K_{r-3}\) burn as well: each of their vertices has two incident burning edges, but at most one chip. Their neighboring \(K_{r-3}\)'s burn as well, until the whole graph burns, contradicting r(D) > 0. Thus G is an r-regular simple graph with gonality strictly smaller than multiplicity-free gonality.

We pose the following as an open question.

Question. Does there exist a 3-regular graph with gon(G) < mfgon(G)?

If G is 3-regular, then every divisor D on G with positive (indeed, nonnegative) rank with degree at most g-1 is equivalent to a divisor D' that places at most 2 chips on each vertex; this is a consequence of work in [3], stated explicitly in the discussion following [2, Lemma 16]. We might hope that by performing chip-firing moves, we could transform such a divisor into a multiplicity-free one. The next example shows that this strategy will not work for all divisors on 3-regular graphs.

Example 5.1. Consider the "loop of loops" \(L_5\) of genus 5. This 3-regular graph is pictured in Figure 15, with six equivalent divisors; in fact, pictured are all effective representatives of an equivalence class of divisors. Letting D refer to any one of these divisors, we have that r(D) > 0, and deg(D) = 4. It turns out that \(L_5\) has gonality 4, as can be shown with an exhaustive Dhar's

Figure 15. The effective representatives of a divisor class of positive rank, with no multiplicity-free representatives.

burning algorithm argument. Thus, even though D achieves gonality, it is not equivalent to any multiplicity-free divisor.

Figure 16. A multiplicity-free divisor on L⁵ achieving gonality.

However, L⁵ does have gon(L5) = mfgon(L5): a multiplicity-free divisor achieving gonality is pictured in Figure 16. Nonetheless, this example illustrates that if we wish to prove that any 3-regular graph has gon(G) = mfgon(G), it will not work to start with an arbitrary divisor achieving gonality and then perform chip-firing moves until it is multiplicity-free.

Acknowledgement

The authors were supported by Williams College, by the 2018 and 2020 iterations of the SMALL REU, and by NSF Grants DMS-1659037 and DMS-2011743. They are grateful to Ivan Aidun, Teresa Yu, and Julie Yuan for many conversations on wheels, antiprisms, and other graphs; to Josh Carlson for reading through a preliminary version of this paper; and to Lisa Cenek, Lizzie Ferguson, Eyobel Gebre, Cassandra Marcussen, Jason Meintjes, Liz Ostermeyer, and Shefali Ramakrishna for help in gonality computation.

References

• [1] I. Aidun, F. Dean, R. Morrison, T. Yu, and J. Yuan. Gonality sequences of graphs. SIAM J. Discrete Math. 35 (2) (2021), 814–839.
• [2] I. Aidun and R. Morrison. On the gonality of Cartesian products of graphs. Electron. J. Combin. 27 (4) (2020), #P4.52.
• [3] S. Backman. Riemann-Roch theory for graph orientations. Adv. Math. 309 (2017), 655–691.
• [4] M. Baker. Specialization of linear systems from curves to graphs. Algebra Number Theory 2 (6) (2008), 613–653. With an appendix by Brian Conrad.

• [5] M. Baker and S. Norine. Riemann-Roch and Abel-Jacobi theory on a finite graph. Adv. Math. 215 (2) (2007), 766–788.
• [6] M. Baker and S. Norine. Harmonic morphisms and hyperelliptic graphs. Int. Math. Res. Not. IMRN 15 (2009), 2914–2955.
• [7] G. Cornelissen, F. Kato, and J. Kool. A combinatorial Li-Yau inequality and rational points on curves. Math. Ann. 361 (1-2) (2015), 211–258.
• [8] A. Deveau, D. Jensen, J. Kainic, and D. Mitropolsky. Gonality of random graphs. Involve 9 (4) (2016), 715–720.
• [9] D. Dhar. Self-organized critical state of sandpile automaton models. Phys. Rev. Lett. 64 (14) (1990), 1613–1616.
• [10] M. Echavarria, M. Everett, R. Huang, L. Jacoby, R. Morrison, and B. Weber. On the scramble number of graphs. Discrete Appl. Math. 310 (2022), 43–59.
• [11] D. Gijswijt, H. Smit, and M. van der Wegen. Computing graph gonality is hard. Discrete Appl. Math. 287 (2020), 134–149.
• [12] N. Speeter. The gonality of rook graphs, preprint, 2022.
• [13] J. van Dobben de Bruyn. Reduced divisors and gonality in finite graphs. Bachelor's thesis, Mathematisch Instituut, Universiteit Leiden, 2012.
• [14] J. van Dobben de Bruyn and D. Gijswijt. Treewidth is a lower bound on graph gonality. Algebr. Comb. 3 (4) (2020), 941–953.

Appendix A. Lemmas for the wheel graph

Proposition Appendix A.1. For any positive integer n, we have \(\lceil \sqrt{n} \rceil - 1 + \left\lceil \frac{n}{\lceil \sqrt{n} \rceil} \right\rceil = \lfloor \sqrt{n} \rfloor - 1 + \left\lceil \frac{n}{\lceil \sqrt{n} \rceil} \right\rceil\).

Proof. The claim is immediately true for square numbers n, since everything being rounded is already an integer. Thus, assume n is not a square number. Let \(s = \lfloor \sqrt{n} \rfloor\). It suffices to show \(\lceil \frac{n}{s} \rceil = \lceil \frac{n}{s+1} \rceil + 1\). Note that \(s^2 < n\) and since n is an integer, \((s+1)^2 - 1 \ge n \Rightarrow s^2 + 2s \ge n\). Suppose \(n \le s^2 + s\). Then it follows that

\[s < \frac{n}{s} \le s + 1\] \[\Rightarrow \left\lceil \frac{n}{s} \right\rceil = s + 1\] \[s - 1 < \frac{n}{s + 1} \le s\] \[\Rightarrow \left\lceil \frac{n}{s + 1} \right\rceil = s\]

Thus, the claim is true.

Suppose \(n > s^2 + s\). Then it follows that

\[s+1 < \frac{n}{s} \le s+2\] \[\Rightarrow \left\lceil \frac{n}{s} \right\rceil = s+2\] \[s < \frac{n}{s+1} < s+1\] \[\Rightarrow \left\lceil \frac{n}{s+1} \right\rceil = s+1\]

And the claim is also true.

Proposition Appendix A.2. Let \(n \ge 3\). We have \(\lfloor \sqrt{n} \rfloor - 1 + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor} \rceil = \lceil \frac{n}{2} \rceil + 1\) if and only if \(n \le 8\) or n = 10.

Proof. We have

\[\lfloor \sqrt{n} \rfloor - 1 + \left\lceil \frac{n}{\lfloor \sqrt{n} \rfloor} \right\rceil < \sqrt{n} + \frac{n}{\lfloor \sqrt{n} \rfloor}\] \[= n \cdot \left( \frac{1}{\sqrt{n}} + \frac{1}{\lfloor \sqrt{n} \rfloor} \right)\] \[\leq n \cdot \frac{2}{\lfloor \sqrt{n} \rfloor}.\]

Note that for \(n \geq 16\), we have \(\frac{2}{\lfloor \sqrt{n} \rfloor} \leq \frac{2}{\lfloor \sqrt{16} \rfloor} = \frac{1}{2}\), so we have

\[\lfloor \sqrt{n} \rfloor - 1 + \left\lceil \frac{n}{\lfloor \sqrt{n} \rfloor} \right\rceil < \frac{n}{2} < \left\lceil \frac{n}{2} \right\rceil + 1.\]

Thus it suffices to compare the two formulas for \(3 \le n \le 15\). By direct computation we find equality precisely when \(3 \le n \le 8\) and n = 10.