Hartnell and Rall recently introduced the domatic number game. Alice and Bob color the vertices of a graph from a palette [\(k\)], and Alice wins if every color class is a dominating set at the end of the game. The largest winning palette size is denoted by \(\mathop{\mathrm{dom}}\nolimits_{g}(G)\) when Alice moves first and by \(\mathop{\mathrm{dom}}\nolimits’_{g}(G)\) when Bob moves first. Hartnell and Rall asked how these parameters behave under edge and vertex removal, and they also asked whether Bob can win with \(k\) colors while Alice wins with \(k+1\) colors. We give short answers. First, Alice-winning palettes are downward closed: if Alice can win with \(k+1\) colors, then she can win with \(k\) colors, in both versions of the game. Thus the proposed palette-size pathology never occurs. Second, if \(H\) is a spanning subgraph of \(G\), then
\[
\mathop{\mathrm{dom}}\nolimits_{g}(H)\le \mathop{\mathrm{dom}}\nolimits_{g}(G),\qquad \mathop{\mathrm{dom}}\nolimits’_{g}(H)\le \mathop{\mathrm{dom}}\nolimits’_{g}(G).
\]
Thus edge deletion can never increase either invariant, and the inequalities may be strict. Finally, vertex deletion is not monotone: it can increase or decrease either invariant. Deleting one vertex can even increase either invariant by an arbitrarily large amount.
The domatic number \(\operatorname{dom}(G)\) of a graph \(G\) is the largest number of pairwise disjoint dominating sets into which \(V(G)\) can be partitioned. Hartnell and Rall [2] introduced a game version of this invariant.
Fix a positive integer \(k\). Alice and Bob take turns choosing an uncolored vertex of \(G\) and assigning it a color from
At the end of the game, the color classes
partition \(V(G)\), where \(V_i\) is the set of vertices colored \(i\). Alice wins if every \(V_i\) is a dominating set of \(G\). Equivalently, Alice wins if every closed neighborhood contains every color. Bob wins if at least one closed neighborhood misses at least one color.
There are two versions of the game. In the A-game, Alice moves first, and the largest \(k\) for which Alice can force a win is denoted \(\mathop{\mathrm{dom}}\nolimits_g(G)\). In the B-game, Bob moves first, and the corresponding number is denoted \(\mathop{\mathrm{dom}}\nolimits’_g(G)\). Hartnell and Rall computed these values for several graph classes, including trees, paths, cycles, complete graphs, complete bipartite graphs, and some grid graphs. They ended their paper with several natural questions. We focus on the following two.
Question 1.1 (Hartnell–Rall [2]). How does edge or vertex removal affect the game domatic number?
Question 1.2 (Hartnell–Rall [2]). Can there be a graph \(H\) and a positive integer \(k\) such that Bob wins with palette \([k]\), but Alice wins with palette \([k+1]\)? The question may be asked for either the A-game or the B-game.
The second question is especially natural because related monotonicity questions in coloring games are subtle. In the domatic number game, however, the answer is simple. There are no restrictions on which colors may be played during the game. A move is legal exactly when the chosen vertex is still uncolored. This means that colors can be merged without making any move illegal. We use this observation to prove that if Alice wins with \(k+1\) colors, then Alice also wins with \(k\) colors. So Bob cannot win with \(k\) colors while Alice wins with \(k+1\) colors.
We also give a clean answer for edge deletion. If \(H\) is obtained from \(G\) by deleting edges but not vertices, then every closed neighborhood in \(H\) is contained in the corresponding closed neighborhood in \(G\). Thus a coloring that wins on \(H\) automatically wins on \(G\). Since the set of legal moves is the same on the two graphs, Alice can use a winning strategy for \(H\) on \(G\). Therefore edge deletion can never increase \(\mathop{\mathrm{dom}}\nolimits_g\) or \(\mathop{\mathrm{dom}}\nolimits’_g\).
After the submission of this manuscript, English and Swan [1] independently obtained the palette-size and edge-deletion monotonicity results proved here. They also independently observed that deleting a single vertex can increase the game domatic number by an arbitrarily large amount.
Vertex deletion behaves differently. Removing a vertex changes the board and changes the closed neighborhoods. We show by small examples that no monotone statement is possible. Deleting a vertex can increase \(\mathop{\mathrm{dom}}\nolimits_g\), decrease \(\mathop{\mathrm{dom}}\nolimits_g\), increase \(\mathop{\mathrm{dom}}\nolimits’_g\), or decrease \(\mathop{\mathrm{dom}}\nolimits’_g\). The increase caused by deleting one vertex can be arbitrarily large.
The paper is organized as follows. Section 2 recalls the notation and a few values from [2]. Section 3 proves the palette monotonicity result. Section 4 proves edge-deletion monotonicity and gives an example where the inequality is strict. Section 5 gives the vertex-deletion examples. We conclude with a brief discussion of the disjoint-union question.
All graphs are finite and simple. If \(x\in V(G)\), then
denotes the open neighborhood of \(x\), and
denotes the closed neighborhood of \(x\). When the graph is clear, we write \(N(x)\) and \(N[x]\).
Definition 2.1. Let \(G\) be a graph and let \(k\ge 1\). A completed coloring
is winning for Alice if every color appears in every closed neighborhood. In symbols,
Equivalently, each color class \(c^{-1}(i)\) is a dominating set of \(G\).
The following formulas are due to Hartnell and Rall [2]. We will use them only for examples. For complete graphs,
For paths,
We shall also use the following consequence of their Proposition 3.3: if \(G\) has minimum degree one, then
We first answer the palette-size question. The point is that having more colors cannot make Alice stronger. More precisely, if Alice can win with \(k+1\) colors, then she can also win with \(k\) colors. The proof is simply to merge the last color into the first color.
Theorem 3.1 (Downward closure of Alice-winning palettes). Let \(G\) be a graph and let \(k\ge 1\). If Alice has a winning strategy for the A-game on \(G\) with palette \([k+1]\), then Alice has a winning strategy for the A-game on \(G\) with palette \([k]\). The same statement holds for the B-game.
Proof. We prove the A-game statement. The B-game proof is the same.
Assume Alice has a winning strategy \(\mathcal S\) for the A-game with colors
Define
by
So \(\phi\) simply merges color \(k+1\) into color \(1\).
Alice now plays the \(k\)-color game as follows. She imagines that she is playing the \((k+1)\)-color game using the strategy \(\mathcal S\). If \(\mathcal S\) tells her to color a vertex with color \(i\), she colors that same vertex with color \(\phi(i)\) in the real game.
This simulation is always legal. The only legal requirement in the domatic number game is that the chosen vertex has not already been chosen. Also, Bob’s real moves use only colors from \([k]\), so we may view them as moves in the simulated \((k+1)\)-color game as well.
At the end of the simulated game, \(\mathcal S\) wins. Therefore every closed neighborhood contains every simulated color:
where \(c_{\rm sim}(N_G[x])\) is the set of colors appearing in \(N_G[x]\) in the simulated game. The real coloring is obtained by applying \(\phi\). Thus, for every \(x\in V(G)\),
Every color in \([k]\) appears in every closed neighborhood, so Alice wins the real \(k\)-color game. \(\square\)
Remark 3.2. For every graph \(G\), the palette sizes for which Alice wins the A-game are exactly
and the palette sizes for which Alice wins the B-game are exactly
In particular, there is no graph \(H\) and positive integer \(k\) such that Bob wins with palette \([k]\) but Alice wins with palette \([k+1]\), in either the A-game or the B-game.
Remark 3.3. This is the main reason the domatic number game is easier here than the coloring game. In a coloring game, adding or merging colors can change which moves are legal. In the domatic number game, legality does not depend on the colors already used near a vertex. That is why the color-merging proof works.
We now turn to edge deletion. The result is monotone in the expected direction: deleting edges cannot help Alice.
Theorem 4.1 (Spanning-subgraph monotonicity). Let \(H\) be a spanning subgraph of \(G\). In other words,
Then
Equivalently, deleting edges can never increase either game domatic number.
Proof. Suppose Alice wins on \(H\) with palette \([k]\), in either the A-game or the B-game. She uses the same strategy on \(G\). This is legal because \(H\) and \(G\) have the same vertex set and legal moves do not depend on the edge set. Every color class that dominates \(H\) also dominates \(G\), since
Thus the same strategy wins on \(G\), proving both inequalities. \(\square\)
Example 4.2 (Deleting one edge can matter). Let \(G=K_3\), and delete one edge. The resulting graph is \(P_3\). By (1), (2), (3), and (4),
So one edge deletion can strictly decrease both invariants.
Vertex deletion has no clean monotonicity rule. The next two propositions show that deleting one vertex can help Alice or hurt Alice, for both versions of the game.
Proposition 5.1. For every integer \(r\ge 1\), there is a graph \(G_r\) and a vertex \(v\in V(G_r)\) such that
There is also a graph \(G_r’\) and a vertex \(v’\in V(G_r’)\) such that
Proof. For the A-game, start with \(K_{2r+1}\) and attach one new leaf \(v\) to one clique vertex. Call the resulting graph \(G_r\). Then \(G_r\) has even order and minimum degree one, so (5) gives
After deleting \(v\), we obtain \(K_{2r+1}\), and hence
Thus \(\mathop{\mathrm{dom}}\nolimits_g(G_r-v)-\mathop{\mathrm{dom}}\nolimits_g(G_r)=r\).
For the B-game, start with \(K_{2r}\) and attach one new leaf \(v’\) to one clique vertex. Call the resulting graph \(G_r’\). Then \(G_r’\) has odd order and minimum degree one, so (6) gives
Deleting \(v’\) gives \(K_{2r}\), so
Therefore \(\mathop{\mathrm{dom}}\nolimits’_g(G_r’-v’)-\mathop{\mathrm{dom}}\nolimits’_g(G_r’)=r\). \(\square\)
Proposition 5.2. There is a graph \(G\) and a vertex \(v\in V(G)\) such that
There is also a graph \(G’\) and a vertex \(v’\in V(G’)\) such that
Proof. For the A-game, take \(G=K_3\). Deleting any vertex gives \(K_2\), and
For the B-game, take \(G’=K_4\). Deleting any vertex gives \(K_3\), and
\(\square\)
Remark 5.3. Neither \(\mathop{\mathrm{dom}}\nolimits_g\) nor \(\mathop{\mathrm{dom}}\nolimits’_g\) is monotone under vertex deletion. For each invariant, deleting one vertex can increase or decrease the invariant, and the increase caused by deleting one vertex can be arbitrarily large. Determining the largest possible decrease caused by deleting a single vertex remains open; English and Swan [1, Question 5.3] also pose this question.
One question of Hartnell and Rall [2] not addressed here concerns disjoint unions. In a game played on \(G_1\cup G_2\), a player may move in one component while the other component remains unchanged. Consequently, the play induced on an individual component need not correspond consistently to either the A-game or the B-game. The arguments used in this paper therefore do not yield a general formula for \(\mathop{\mathrm{dom}}\nolimits_g(G_1\cup G_2)\) or \(\mathop{\mathrm{dom}}\nolimits’_g(G_1\cup G_2)\), and determining the behavior of these parameters under disjoint unions remains open.