Impartial Geodetic Removing Games on Graphs
June 03, 2026
Abstract
A subset of the vertex set of a graph is geodetically convex if it contains every vertex on any shortest path between two elements of the subset. The convex hull of a set of vertices is the smallest convex set containing the set. We study two games in which two players take turns selecting vertices of a graph until the convex hull of the jointly unselected vertices is too small. The last player to move is the winner. The achievement game ends when the convex hull of the jointly unselected vertices is not the vertex set. In the avoidance game, the convex hull of the jointly unselected vertices must always be the vertex set. We study the nim-values for several graph families, including cycle graphs, hypercube graphs, complete multipartite graphs, wheel graphs, generalized wheel graphs, and graphs with a unique minimal generating set.
1 Introduction↩︎
Given a subset of vertices \(S\) in a finite simple graph, the set of vertices lying on any shortest path between elements of \(S\) is known as the geodetic closure of \(S\). This concept formed the basis for a pair of impartial combinatorial games introduced by Harary [1]. In these achievement and avoidance building games, two players alternately select unselected vertices, updating the geodetic closure of their joint selections at each turn. The achievement game ends as soon as the geodetic closure becomes the vertex set, whereas the avoidance game does not allow the geodetic closure to be equal to the vertex set. The player who is unable to move loses the games. Variants of geodetic closure building games have been extensively studied across standard graph families, including cycles, wheels, complete multipartite graphs, and split graphs [2]–[7].
In [8], we introduced a variation of the geodetic closure games that uses the convex hull. A vertex subset \(S\) is geodetically convex if it contains all vertices along shortest paths between its members. The convex hull of \(S\) is the smallest geodetically convex set containing \(S\). Despite its name, the geodetic closure is only a pre-closure, while the convex hull is a closure operator. Although the convex hull and geodetic closure operators are identical for various graph families, they diverge on others. While most of the results in the literature have restricted their focus to the outcomes of geodetic closure games, we determined the nim-values of convex hull games across multiple graph families.
The geodetic closure and convex hull games described above are examples of building hypergraph games, which were formalized in [9]. In contrast, removing hypergraph games represent a complementary variation of hypergraph games. We initiated a study of removing games played on graphs using the convex hull operator in [10]. For the removing paradigm, players select vertices from a finite graph, steadily shrinking the pool of unchosen vertices until their convex hull becomes too small. Specifically, the achievement game \(\text{TER}\) (terminate) is won by the player who is able to select a vertex such that the convex hull of the unselected vertices no longer equals the vertex set. The avoidance game \(\text{DNT}\) (do not terminate) requires the players to keep the convex hull of the unselected vertices equal to the vertex set. In [10], we determined the nim-value of these games for the family of grid graphs and also provided some results for higher-dimensional lattice graphs.
In the present paper, we compute nim-values for \(\text{TER}\) and \(\text{DNT}\) across an array of graph classes, such as complete split, corona, block, cycle, hypercube, complete multipartite, wheel, and generalized wheel graphs. To accomplish this, our analysis employs several combinatorial strategies, including characterizing maximal nonterminating sets, establishing structural equivalences via option-preserving maps, reducing positions to the game of Dawson’s Chess, and using case analysis diagrams to describe complex winning strategies.
For a foundational treatment of impartial game theory, readers are directed to [11]–[13]. The remainder of this paper is organized as follows. Section 2 establishes preliminary definitions regarding transversals, impartial games, and geodetic convexity. Section 3 formally defines the \(\text{TER}\) and \(\text{DNT}\) removing games. In Section 4, we resolve the nim-values for graphs possessing a unique minimal generating set. Section 5 details our nim-value computations for several graph families. Finally, Section 6 highlights open questions and potential avenues for future research.
2 Preliminaries↩︎
We recall some terminology and notation.
2.1 Notation↩︎
If \(f:X\to Y\) and \(A\subseteq X\), then we often use the standard \(f(A):=\{f(a)\mid a\in A\}\) notation for the image of \(A\). As a special case, for a family \(\mathcal{A}\) of subsets of \(X\) we define \[\complement(\mathcal{A}):=\{A^c\mid A\in\mathcal{A}\},\] where \(A^c=X\setminus A\) is the complement of \(A\).
We define the parity of the integer \(k\) as \(\text{pty}(k):=k\!\mod2\). The cardinality of a set \(A\) is denoted by \(|A|\), and we write \(\text{pty}(A):=\text{pty}(|A|)\) for the parity of a set.
2.2 Transversals↩︎
Let \(\mathcal{A}\) be a family of sets. A set \(T\) is a transversal of \(\mathcal{A}\) if \(T \cap A \not= \emptyset\) for all \(A \in \mathcal{A}\). We define \(\mathrm{Tr}(\mathcal{A})\) to be the set of minimal transversals of \(\mathcal{A}\). Transversals are sometimes called blocking sets, in which case \(\mathrm{Tr}(\mathcal{A})\) is called the blocker of \(\mathcal{A}\).
Example 1. One can verify that \[\mathrm{Tr}(\left\{\{1,2\}, \{2,3,4\}, \{2,3,5\}\right\})=\{\{2\},\{1,3\},\{1,4,5\}\}.\] The special cases \(\mathrm{Tr}( \emptyset ) = \{ \emptyset\}\) and \(\mathrm{Tr}( \{ \emptyset \} )= \emptyset\) play important roles.
A family \(\mathcal{A}\) of sets is a Sperner family or clutter if no element of \(\mathcal{A}\) contains another element of \(\mathcal{A}\). If \(\mathcal{A}\) is a Sperner family, then \(\mathrm{Tr}(\mathrm{Tr}(\mathcal{A}))=\mathcal{A}\).
2.3 Impartial games↩︎
Our general references for combinatorial game theory are [11], [13].
In an impartial game, two players take turns to replace the current position of the game with one of its options. The game ends when the current position has no options. The player unable to move is the loser. Every game must finish in finitely many steps. In particular, no position can be reached twice. We model an impartial game with a gamegraph, which is a finite set \(\mathsf{G}\) of positions and a collection \(\text{Opt}(p)\subseteq\mathsf{G}\) of options for each position \(p\in\mathsf{G}\). A gamegraph has a starting position, which is a unique position not in the option set of any position. We visualize gamegraphs with a diagram showing an arrow from a position to every option of that position. Game play is moving from one vertex to another along the arrows. The game ends when a position without options is reached.
The minimum excludant \(\text{mex}(A)\) of a set \(A\) of non-negative integers is the smallest non-negative integer that is not in \(A\). The nim-value \(\text{nim}(p)\) of a position \(p\) is defined recursively as the minimum excludant of the nim-values of the options of \(p\). That is, \[\text{nim}(p):=\text{mex}(\text{nim}(\text{Opt}(p))).\] The nim-value of the game is the nim-value of the starting position.
A position is terminal if it has no options. A terminal position \(p\) has nim-value \(\text{nim}(p)=\text{mex}(\text{nim}(\emptyset))=\text{mex}(\emptyset)=0\). A position \(p\) is losing for the player about to move (\(P\)-position) if \(\text{nim}(p)=0\) and winning (\(N\)-position) otherwise. The winning strategy is to always move to a losing option with nim-value \(0\) if available.
The game sum \(\mathsf{G}+\mathsf{H}\) has position set \(\mathsf{G}\times\mathsf{H}\) with \(\text{Opt}(p,q):=(\text{Opt}(p)\times\{q\})\cup(\{p\}\times\text{Opt}(q))\). A convenient way to show that \(\text{nim}(\mathsf{G})=k\) is to find a strategy for the second player to win \(\mathsf{G}+*k\), where \(*k\) is the nimber with \(\text{Opt}(*k)=\{*0,\ldots,*(k-1)\}\).
We will often use another useful result.
1. [8] If every terminal position of an impartial game \(\mathsf{G}\) has the same parity \(r\), then \(\text{nim}(\mathsf{G})=r\).
2.4 Option-preserving maps↩︎
A function \(f:\mathsf{G}\to\mathsf{H}\) between two gamegraphs is option-preserving [14], [15] if \(\text{Opt}(f(p))=f(\text{Opt}(p))\) for all \(p\in\mathsf{G}\). We use option-preserving maps to study a complicated game through its simpler image. This is possible because of the following result.
2. [15] If \(f:\mathsf{G}\to\mathsf{H}\) is option-preserving, then \(\text{nim}(f(p))=\text{nim}(p)\) for all \(p\in\mathsf{G}\).
This implies that if the starting position of \(\mathsf{G}\) maps to the starting position of \(\mathsf{H}\), then \(\text{nim}(\mathsf{G})=\text{nim}(\mathsf{H})\). Note that a surjective option-preserving map always takes starting positions to starting positions.
2.5 Geodetic convexity↩︎
A graph is an ordered pair \(G=(V,E)\), where \(V\) is a finite nonempty set of vertices and \(E\subseteq 2^V\) is the set of edges. We do not allow loop edges. A geodesic of a graph is a shortest path between two vertices. A set \(P\) of vertices of a graph \((V,E)\) is called geodetically convex or simply convex if it contains all vertices along the geodesics connecting two vertices of \(P\). The convex hull \([P]:=\bigcap\{K\mid P\subseteq K, K \text{ is convex} \}\) of \(P\) is the smallest convex set containing \(P\). The convex hull function \(P\mapsto[P]:2^V\to 2^V\) is a closure operator. In particular, \([P]\) is convex if and only if \([P]=P\). A comprehensive reference about geodetic convexity is [16].
We say that a set \(P\) of vertices is generating if \([P]=V\). Otherwise, \(P\) is called nongenerating. The family of maximal nongenerating sets is denoted by \(\mathcal{N}\) while the family of minimal generating sets is denoted by \(\mathcal{G}\).
We say that a set \(P\) of vertices is terminating if \([P^c]\ne V\). Otherwise, \(P\) is called nonterminating. The family of maximal nonterminating sets is denoted by \(\mathcal{N}^\star\) while the family of minimal terminating sets is denoted by \(\mathcal{G}^\star\). The generating and terminating sets are Sperner families that are related according to the following result from [9].
3. For all graphs, \(\mathcal{N}^\star=\complement(\mathcal{G})\), \(\mathcal{N}=\complement(\mathcal{G}^\star)\), and \(\mathcal{G}^*=\mathrm{Tr}(\mathcal{G})\).
4. The relationships can be summarized by the following diagram: \[\mathcal{N}^\star \overset{\complement}{\longleftrightarrow} \mathcal{G} \overset{\mathrm{Tr}}{\longleftrightarrow} \mathcal{G}^\star \overset{\complement}{\longleftrightarrow} \mathcal{N}\]
Example 2. The kite graph \(G\) with its generating and terminating sets is shown in Figure [fig:kite].
3 Removing games↩︎
Our goal is to study two impartial removing hypergraph games [9]. We play both games on a graph \(G\) with vertex set \(V\) and edge set \(E\). Two players take turns selecting previously unselected vertices of \(G\) until certain conditions are met. Each game position is the set \(P\) of jointly selected vertices.
The achievement game terminate \(\text{TER}(G)\) ends as soon as the set of unchosen vertices of \(G\) no longer generates \(V\). So the player who first removes a vertex that prevents generating the whole vertex set wins. This happens as soon as \(P\) is terminating. That is, \(G\subseteq P\) for some \(G\in\mathcal{G}^*\).
In the avoidance game do not terminate \(\text{DNT}(G)\), each position \(P\) must be nonterminating. That is, \(P\subseteq N\) for some \(N\in\mathcal{N}^*\). The game ends if no additional vertex can be selected while maintaining this condition.
Example 3. The gamegraphs for the path graph \(P_3\) with \(V=\{u,v,w\}\) are shown in Figure [fig:P3]. Note that \(\mathcal{G}^*=\{\{u\},\{w\}\}\) and \(\mathcal{N}^\star=\{\{v\}\}\).
Example 4. Let \(G\) be the graph with a single vertex \(v\), so that \(\mathcal{G}^*=\{\{v\}\}\) and \(\mathcal{N}^*=\{\emptyset\}\). The nim-value of \(\text{DNT}(G)\) is \(0\) since the only position of the game is \(\emptyset\). The nim-value of \(\text{TER}(G)\) is \(1\) since the game has only two positions \(\emptyset\) and \(\{v\}\).
The terminal positions of \(\text{DNT}(G)\) are the elements of \(\mathcal{N}^*\). Hence we have the following consequence of Proposition 1.
5. If every element of \(\mathcal{N}^*\) has the same parity \(r\), then \(\text{nim}(\text{DNT}(G))=r\).
Example 5. Consider the wheel graph \(W_5\). Representative quotient gamegraphs for \(\text{DNT}(W_5)\) and \(\text{TER}(W_5)\) are given in Figure [fig:W5]. In this quotient, we identified geometrically congruent positions. The canonical quotient map is option-preserving. In both cases, we have labeled positions with their corresponding nim-values. Every position of \(\text{DNT}(W_5)\) contains two unmarked antipodal noncentral vertices that generate \(W_5\). The terminal positions of \(\text{TER}(W_5)\) do not have such pairs of unmarked vertices.
4 Graphs with a unique minimal generating set↩︎
Graphs with a unique minimal generating set are common and relatively easy to analyze. A vertex is called simplicial if the subgraph induced by the neighbors of the vertex is a complete graph. A generating set contains every simplicial vertex by [8]. Furthermore, if \(L\) is a generating set that contains only simplicial vertices, then \(\mathcal{G}=\{L\}\) by [8].
Example 6. Figure [fig:ugs] shows a graph with a generating set \(L=\{u,v,w\}\) consisting of the simplicial vertices. Hence \(\mathcal{G}=\{L\}\).
The next result follows easily by either using the definitions of generating and terminating or by utilizing the approach outlined in Remark 4.
6. If \(\mathcal{G}=\{L\}\), then \(\mathcal{G}^\star=\{\{l\}\mid l\in L\}\) and \(\mathcal{N}^\star=\{L^c\}\).
The following is a consequence of Proposition 5.
7. If \(\mathcal{G}=\{L\}\), then \(\text{nim}(\text{DNT}(G))=\text{pty}(L^c)\).
Using our notation, the next result is a special case of [9].
8. If \(\mathcal{N}^*\) is pairwise disjoint, \(\{\text{pty}(P) \mid P\in\mathcal{N}^*\}=\{a\}\), and \(V(G)\ne\bigcup\mathcal{N}^*\), then \(\text{nim}(\text{TER}(G))=a+1\).
This together with Proposition 6 immediately implies the following.
9. If \(\mathcal{G}=\{L\}\), then \(\text{nim}(\text{TER}(G))=1+\text{pty}(L^c)\).
4.1 Complete split graphs↩︎
A complete split graph is the join \(K_m +\overline{K_n}\) of the complete graph \(K_m\) and the complement graph \(\overline{K_n}\). Recall from [8] that \(\mathcal{G}=\{V(\overline{K}_n)\}\) for \(n\geq 2\). So we have the following by Propositions 7 and 9.
10. If \(G=K_m+\overline{K}_n\) and \(n\ge 2\), then \(\text{nim}(\text{DNT}(G))=\text{pty}(m)\) and \(\text{nim}(\text{TER}(G))=1+\text{pty}(m)\).
Example 7. The diamond graph shown in Figure [fig:diamond] is the complete split graph \(G:=K_2+\overline{K_2}\) with \(\mathcal{G}=\{\{x,y\}\}\) and \(\mathcal{N}^*=\{\{u,v\}\}\). We have \(\text{nim}(\text{DNT}(G))=\text{pty}(\{u,v\})=0\) and \(\text{nim}(\text{TER}(G))=1+\text{pty}(\{u,v\})=1\).
4.2 Corona graphs↩︎
The corona \(H \circ K_1\) is formed from the graph \(H\) by adding for each \(v \in V(H)\) a new vertex \(v'\) and a new edge \(vv'\). A corona graph has a unique minimal generating set \(L=\{v'\mid v\in V(G)\}\) by [8]. Hence we have the following.
11. If \(H\) is a nontrivial graph and \(G=H\circ K_1\), then \(\text{nim}(\text{DNT}(G))=\text{pty}(V)\) and \(\text{nim}(\text{TER}(G))=1+\text{pty}(V)\).
4.3 Block graphs↩︎
A block of a graph is a maximal connected subgraph without a cut vertex. A block graph or clique tree is a graph whose blocks are complete graphs. A vertex is called simplicial if the subgraph induced by the neighbors of the vertex is a complete graph. The simplicial vertices of a block graph form the unique minimal generating set \(L\) by [8].
Example 8. The complete graph \(K_n\) is a block graph with \(L=V\). Hence \(\text{pty}(L^c)=0\), and so \(\text{nim}(\text{DNT}(K_n))=0\) and \(\text{nim}(\text{TER}(K_n))=1\).
Example 9. A generalized windmill graph \(G = \mathop{\mathrm{Wd}}(\vec{n})\) for \(\vec{n} = (n_1 , \ldots , n_{\ell} ) \in \mathbb{N}^{\ell}_{\ge 2}\) and \(\ell \ge 2\) is the block graph built from the complete graphs \(K_{n_1} , \ldots , K_{n_{\ell}}\) by gluing at a common vertex \(c\). Since \(L=\{c\}^c\), \(\text{nim}(\text{DNT}(G))=1-\text{pty}(V)\) and \(\text{nim}(\text{TER}(G))=2-\text{pty}(V)\).
Example 10. A forest graph \(G\) is a block graph where \(L\) is the set of leaves. In particular, \(\text{nim}(\text{DNT}(P_n))=\text{pty}(n)\) and \(\text{nim}(\text{TER}(P_n))=1+\text{pty}(n)\) for the path graph \(P_n\), while \(\text{nim}(\text{DNT}(K_{1,n}))=1\) and \(\text{nim}(\text{TER}(K_{1,n}))=1\) for the star graph \(K_{1,n}\).
5 Graph families↩︎
We study the impartial games on several graph families.
5.1 Cycle graphs↩︎
For \(n\ge 4\), we define \(C_n\) to be the cycle graph with vertex set \(\{v_1,\ldots,v_n\}\) and \(v_i\) is adjacent to \(v_{i+1}\) if the indices are considered modulo \(n\). Note that if \(n=3\), then the construction gives the complete graph \(K_3\).
12. For cycle graphs with odd \(n\), \[\mathcal{G}=\{\{v_{i},v_j,v_{k}\} \mid i < j < k \text{ and } j-i,k-j,i+n-k\le(n-1)/2 \}.\]
Proof. It is easy to see that two vertices cannot generate. The condition on the \(i,j,k\) guarantees that the unique geodesic between two of the chosen vertices does not contain the third chosen vertex. Hence every such \(\{v_i,v_j,v_k\}\) is a generating set. Every generating set must contain three such vertices. ◻
Example 11. For \(C_5\), the maximum directed distance allowed between consecutive vertices in a minimal generating set is \((5-1)/2=2\). So \[\begin{align} \mathcal{G} &=\{\{v_1,v_3,v_4\},\{v_2,v_4,v_5\},\{v_1,v_3,v_5\},\{v_1,v_2,v_4\},\{v_2,v_3,v_5\}\}, \\ \mathcal{N}^* &=\complement(\mathcal{G})=\{\{v_2,v_5\},\{v_1,v_3\},\{v_2,v_4\},\{v_3,v_5\},\{v_1,v_4\}\}, \\ \mathcal{G}^* &=\mathrm{Tr}(\mathcal{G})=\{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_4,v_5\},\{v_1,v_5\}\}. \end{align}\] Note that \(\mathcal{N}^*\) only contains even sets. Also note that the second player can win \(\text{TER}(C_5)\) after two moves since every vertex is contained in a two-element terminating set.
13. For cycle graphs, \(\text{nim}(\text{DNT}(C_{n}))=0\).
Proof. If \(n\) is even, then the second player wins by always selecting the vertex antipodal to the vertex selected by the first player. The game ends when there are two antipodal unselected vertices remaining. If \(n\) is odd, then \(\mathcal{N}^*=\complement(\mathcal{G})\) contains sets with size \(n-3\), so the result follows from Proposition 5. ◻
14. For cycle graphs with even \(n\), \(\text{nim}(\text{TER}(C_{n}))=0\).
Proof. The second player wins by selecting vertices antipodal to the selection of the first player until there are only four unselected vertices remaining. In the last move the second player selects a vertex that is not antipodal to the vertex selected by the first player. ◻
The case where \(n\) is odd is surprisingly tricky for \(\text{TER}(C_n)\). We have verified the following conjecture up to \(n=21\) via computer.
15. For cycle graphs with odd \(n\), \(\text{nim}(\text{TER}(C_{n}))=0\).
5.2 Hypercube graphs↩︎
For \(n\geq 3\), we define the set of binary strings of length \(n\) via \[\{0,1\}^n := \{a_1a_2\cdots a_n \mid a_k \in \{0,1\} \}.\] The hypercube graph \(Q_n\) of dimension \(n\) is the graph whose vertices are elements of \(\{0,1\}^n\) with two binary strings connected by an edge exactly when they differ by a single digit. We say that two binary strings \(a_1a_2\cdots a_n\) and \(b_1b_2\cdots b_n\) are antipodal if \(a_i\neq b_i\) for all \(1\leq i\leq n\).
16. For hypercube graphs, \(\text{nim}(\text{DNT}(Q_{n}))=0\).
Proof. Each pair of antipodal vertices is a minimal generating set by [8]. Then the second player wins by always selecting the antipodal vertex after the first player’s selection. The game ends when there is a single pair of antipodal vertices remaining. ◻
17. For hypercube graphs, \(\text{nim}(\text{TER}(Q_{n}))=0\).
Proof. The second player always selects the antipodal vertex after the first player’s selection until there are two pairs of antipodal vertices remaining. After the first player chooses one of the remaining four vertices, the second player ends the game by selecting one of the two remaining vertices not antipodal to the first player’s last choice. ◻
5.3 Complete multipartite graphs↩︎
In this section we consider the complete multipartite graph \(G=K_{m_1,\ldots,m_k}\) with \(k\ge2\), \(m_1\le m_2\le \cdots \le m_k\) and \(m_k\ge 2\). The parts of \(G\) that contain only one vertex are called small, while the parts containing at least two vertices are called large. We let \(\sigma\) be the number of small parts, that is, \(\sigma:=|\{i\mid m_i=1\}|\). We also let \(\lambda\) be the number of large parts, that is, \(\lambda:=|\{i\mid m_i\ge 2\}|\). Note that \(\lambda\geq 1\) by definition of a complete multipartite graph.
If \(\lambda=1\), then \(G\) is a complete split graph \(K_\sigma+\overline{K_{m_k}}\). So we have the following result by Proposition 10.
18. For complete multipartite graphs with \(\lambda=1\), \(\text{nim}(\text{DNT}(G))=\text{pty}(\sigma)\) and \(\text{nim}(\text{TER}(G))=1+\text{pty}(\sigma)\).
19. For complete multipartite graphs with \(\lambda\ge 2\), \(\mathcal{N}^\star\) consists of sets that are the complement of a set that contains exactly two elements from a single part.
Proof. It is easy to see that \(\mathcal{G}\) consists of the sets that contain exactly two elements from a single part of \(G\). The result now follows from the equality \(\mathcal{N}^\star=\complement(\mathcal{G})\). ◻
20. For complete multipartite graphs with \(\lambda \geq 2\), \(\text{nim}(\text{DNT}(G))=\text{pty}(V)\).
We are going to study \(\text{TER}(K_{m_1,\ldots,m_k})\) for \(\lambda\ge 2\) through an option-preserving image. Let \(U\) be a finite multiset of nonnegative integers. In the multiset terminate game \(\text{TER}(U)\), the players decrease one of the positive elements in \(U\) by 1 in each turn. The game ends when all elements of \(U\) are less than 2.
For a position \(P\) of \(\text{TER}(K_{m_1,\ldots,m_k})\), let \(f(P)\) be the multiset consisting of the number of unmarked vertices in each component. Since \(\mathcal{G}\) consists of the sets that contain exactly two elements from a single part of \(G\), \[f:\text{TER}(K_{m_1,\ldots,m_k})\to\text{TER}(\{\!\!\{ m_1,\ldots,m_k \}\!\!\})\] is an option-preserving map if \(\lambda\ge 2\).
Example 12. Figure [fig:fimage1] shows a play in \(\text{TER}(K_{1,2,2})\) and its image in \(\text{TER}(\{\!\!\{ 1,2,2 \}\!\!\})\) under the option-preserving map \(f\). Note that \(\sigma=1\) and \(\lambda=2\).
The maximum element of the multiset \(U\) is denoted by \(m\). We define \[\sigma:=|\{\!\!\{ u\in U\mid u=1 \}\!\!\}|,\quad \lambda:=|\{\!\!\{ u\in U\mid u\ge 2 \}\!\!\}|, \quad \nu:=|\{\!\!\{ u\in U\mid u=m \}\!\!\}|-1,\] and \(p:=\text{pty}(\|U\|)\), where \(\|U\|:=\sum U\).
Example 13. If \[U=\{\!\!\{ 0,\underbrace{1,1}_\sigma, \underbrace{2,2,2, \overbrace{3,3}^\nu ,3}_\lambda \}\!\!\},\] then \(\sigma=2\), \(\lambda=6\), \(\nu=2\), \(m=3\), and \(p=1\).
If \(U\) is not terminal, then we define \[d:=m-\sum_{u\in U'} (u-1), \text{ with } U':=\{\!\!\{ u\in U \mid u\ge 2 \}\!\!\}\setminus \{\!\!\{ m \}\!\!\}.\] If \(U\) is terminal, then we let \(d:=\infty\). The signature of \(U\) is \(\rho(U):=(p,d)\).
Example 14. If \(U=\{\!\!\{ 1,1,2,3,3 \}\!\!\}\), then \(\rho(U)=(0,0)\) because \(p=\text{pty}(10)=0\), \(U'=\{2,3\}\), and \(d=3-(3-1)-(2-1)\).
If \(U=\{\!\!\{ 0,1,1,1 \}\!\!\}\), then \(\rho(U)=(1,\infty)\) because \(p=\text{pty}(3)=1\) and \(U\) is a terminal position.
21. If \(U\) is not a terminal position in the multiset terminate game and \((p,d)=\rho(U)\), then \[\text{nim}(U)=\begin{cases} 0, & p=0 \text{ and } d \leq 1 \\ 1, & p=0 \text{ and } 2 \leq d \\ 1, & p=1 \text{ and } d \leq 0 \\ 2, & p=1 \text{ and } d \in \{1, 2\} \\ 0, & p=1 \text{ and } 3 \leq d. \end{cases}\]
3pt
|c|c||c||c|c||c|c||c|c||c|c||c|c| & & & & & &
\(p\) & \(d\) & \(\tilde{p}\) & \(\tilde{d}\) & \(\text{nim}(\tilde{U})\)
& \(\tilde{d}\) & \(\text{nim}(\tilde{U})\) & \(\tilde{d}\) & \(\text{nim}(\tilde{U})\) & \(\tilde{d}\) & \(\text{nim}(\tilde{U})\) & \(\text{nim}\circ\text{Opt}\) & mex
& & \(1-p\) & \(d\) & & \(d+1\) & & \(d-1\) & & \(\infty\) & & &
& \(\le-1\) & 1 & \(\le-1\) & 1 & \(\le0\) & 1 & \(\le-2\) & 1 & & & \(\emptyset,\{1\}\) & 0
0 & 0 & 1 & 0 & 1 & 1 & 2 & \(-1\) & 1 & & & \(\emptyset,\{1,2\}\) & 0
0 & 1 & 1 & 1 & 2 & 2 & 2 & 0 & 1 & & & \(\emptyset,\{1,2\}\) & 0
& 2 & 1 & 2 & 2 & 3 & \(\text{\fbox{0}}\) & 1 & 2 & \(\infty\) & \(\text{\fbox{0}}\) & \(\{0\}\),\(\{0,2\}\) & 1
0 & 3 & 1 & 3 & \(\text{\fbox{0}}\) & 4 & \(\text{\fbox{0}}\) & 2 & 2 & & & \(\{0\}\),\(\{0,2\}\) & 1
0 & \(\ge4\) & 1 & \(\ge4\) & \(\text{\fbox{0}}\) & \(\ge5\) & \(\text{\fbox{0}}\) & \(\ge3\) & \(\text{\fbox{0}}\) & & & \(\{0\}\) & 1
& \(\le0\) & 0 & \(\le0\) & \(\text{\fbox{0}}\) & \(\le1\) & \(\text{\fbox{0}}\) & \(\le-1\) & \(\text{\fbox{0}}\) & & & \(\{0\}\) & 1
& 1 & 0 & 1 & \(\text{\fbox{0}}\) & 2 & \(\text{\dbox{1}}\) & 0 & \(\text{\fbox{0}}\) & & & \(\{0,1\}\) & 2
1 & 2 & 0 & 2 & 1 & 3 & \(\text{\fbox{1}}\) & 1 & \(\text{\dbox{0}}\) & \(\infty\) & 0 & \(\{0,1\}\) & 2
& \(\ge3\) & 0 & \(\ge3\) & \(\text{\fbox{1}}\) & \(\ge4\) & \(\text{\fbox{1}}\) & \(\ge2\) & \(\text{\fbox{1}}\) & & & \(\{1\}\) & 0
Proof. We argue by induction on \(\|U\|\). Since \(U\) is not terminal, \(\lambda\ge 1\) and \(m\ge 2\). For a possible option \(\tilde{U}\) of \(U\), we let \((\tilde{p},\tilde{d}):=\rho(\tilde{U})\). Note that \(\|\tilde{U}\|=\|U\|-1\) and \(\tilde{p}=1-p\). Let \(D:=\{\tilde{d}\mid \tilde{U}\in \text{Opt}(U)\}\). It is easy to check that
\(d-1\in D\) if and only if \(\nu=0\);
\(d\in D\) if and only if \(\sigma>0\);
\(d+1\in D\) if and only if \(\lambda>1\);
\(\infty\in D\) if and only if \(\lambda=1\) and \(m=2\).
Table [tab:MultiPartCases] shows the computation of \(\text{nim}(U)=\text{mex}(\text{nim}(\text{Opt}(U)))\) depending on the signature of \(U\) using induction. Each \(\tilde{d}\) column shows a possibility that might or might not occur depending on the condition shown at the top of the column. The corresponding nim-values provide a superset of \(\text{nim}(\text{Opt}(U))\). Nim-values contained in the same type of box indicate that one of the possible \(\tilde{d}\) values must occur. The corresponding nim-values provide a subset of \(\text{nim}(\text{Opt}(U))\). We justify the three nontrivial such claims below.
First, consider the \(\rho(U)=(0,2)\) case. Suppose \(3\not\in D\) and \(\infty\not\in D\). Then \(\lambda=1\) and \(m>2\). This gives the contradiction \(2=d=m>2\).
Next, consider the \(\rho(U)=(0,3)\) case. Suppose \(3\not\in D\) and \(4\not\in D\). Then \(\sigma=0\), \(\lambda=1\) and \(m=3\). This gives the contradiction \(p=1\).
Finally, consider the \(\rho(U)=(1,1)\) case. Since \(\lambda=1\) implies \(d=m>2\), we must have \(\lambda>1\) and so \(2\in D\). Suppose \(1\not\in D\) and \(0\not\in D\). Then \(\sigma=0\) and \(\nu\ge 1\). Since \(p=1\), we must have \(\lambda\ge 3\). This gives the contradiction \(1=d<m-(m-1)-1=0\). ◻
The next result is an immediate consequence.
22. For complete multipartite graphs with \(\lambda \geq 2\), \[\text{nim}(\text{TER}(K_{m_1,\ldots,m_k}))=\begin{cases} 0, & |V| \text{ even and } d \leq 1 \\ 1, & |V| \text{ even and } 2 \leq d \\ 1, & |V| \text{ odd and } d \leq 0 \\ 2, & |V| \text{ odd and } d \in \{1, 2\} \\ 0, & |V| \text{ odd and } 3 \leq d, \end{cases}\] where \(d:=m_k - \sum_{i=1}^{k-1}(m_i-1)\).
5.4 Wheel graphs↩︎
For \(n \geq 5\), we define \(W_n\) to be the wheel graph with \(n\) total vertices \(\{v_1,\ldots,v_{n-1},c\}\), where \(c\) is the center and \(v_i\) is adjacent to \(v_{i+1}\) if the indices are considered modulo \(n-1\).
23. [8] For wheel graphs, \(\mathcal{N}\) consists of the complements of sets containing two neighboring non-central vertices.
The following is an immediate consequence since \(\mathcal{G}^*=\complement(\mathcal{N})\).
Corollary 1. For wheel graphs, \(\mathcal{G}^*\) consists of pairs of neighboring non-central vertices.
We will prove the following result for all \(n\) in Proposition 29. We include the alternate proof because of its simplicity.
24. For wheel graphs with odd \(n\), \(\text{nim}(\text{DNT}(W_{n}))=1\).
Proof. Since \(n\) is odd, \(W_n\) consists of an even cycle with a center vertex. The second player wins \(\text{DNT}(W_n)+*1\) using a pairing strategy, where a vertex on the rim is paired with the antipodal vertex and the center vertex is paired with the stone from \(*1\). The second player always selects the pair of the element chosen by the first player. The symmetry of the pairing of the rim vertices guarantees that the move of the second player prescribed by the strategy is always allowed. ◻
Berlekamp, Conway, and Guy [17] define the game Dawson’s Chess \(\text{DC}(n)\) as follows. Two players start with \(n \geq 0\) pins arranged in a row. They alternate, and on each turn they knock down a pin and any of its standing adjacent neighbors. The player to knock down the last pin wins. Our interest in Dawson’s Chess comes from the next result.
If \(P\) is a position of a removing game, then we use the notation \(\text{DNT}_P(G)\) and \(\text{TER}_P(G)\) to denote the games that start at position \(P\).
25. There is a surjective option-preserving map \(f:\text{DNT}_{\{v_{k}\}}(W_n)\to\text{DC}(n-4)+*1\) for all \(1 \leq k \leq n-1\).
Proof. For notational convenience, assume without loss of generality that \(k=n-2\). The vertices \(v_{n-3}\) and \(v_{n-1}\) cannot be selected since they are adjacent to \(v_{n-2}\) and would result in termination. Thus, the only legal moves in \(\text{DNT}_{\{v_{n-2}\}}(W_n)\) are in \(\{v_1,\ldots, v_{n-4}, c\}\). Let \(p_1,\ldots,p_{n-4}\) be the pins of \(\text{DC}(n-4)\). For \(P\in\text{DNT}_{\{v_{n-2}\}}(W_n)\), let \(f(P)\) be \(\text{DC}(n-4)+*1\) defined as follows. Pin \(p_i\) of \(f(P)\) is knocked down if and only if vertex \(v_j\) of \(W_n\) is selected in \(P\) for some \(|i-j|\le 1\). The single stone from \(*1\) is taken if and only if vertex \(c\) of \(W_n\) is selected in \(P\).
Note that \(f\) is an option-preserving map, since \(v_i \in P\) implies that neither \(v_{i-1}\) nor \(v_{i+1}\) can be selected. Since \(v_i \in P\), this means that \(p_{i-1}\), \(p_i\), and \(p_{i+1}\) have been knocked down in \(f(P)\). Since a vertex \(v_j\) may be selected if and only if neither \(v_{j-1}\) nor \(v_{j+1}\) have been selected, a pin \(p_j\) may be selected if and only if \(p_{j-1}\) and \(p_{j+1}\) have been selected. ◻
The proof of the following is similar to that of the previous result.
26. There is a surjective option-preserving map \(f:\text{DNT}_{\{c,v_{k}\}}(W_n)\to\text{DC}(n-4)\) for all \(1 \leq k \leq n-1\).
Example 15. Figure [fig:map] shows the surjective option-preserving map \[f:\text{DNT}_{\{v_1\}}(W_7)\to\text{DC}(3)+*1.\] The restriction \(\text{DNT}_{\{c,v_1\}}(W_7)\to\text{DC}(3)\) is also surjective and option preserving.
27. For wheel graphs, \[\text{nim}(\text{DNT}(W_n))=\begin{cases} 0, & \text{nim}(\text{DC}(n-4))=0\\ 1, & \text{otherwise}. \end{cases}\]
Proof. Without loss of generality, the first player will select either \(c\) or \(v_{n-1}\) on the first move. This creates position \(P=\{c\}\) or \(Q=\{v_{n-1}\}\), respectively, as shown in Figure [fig:WheelDNTCases]. In position \(P\) the second player will select a rim vertex, which creates a position equivalent to \(\text{DC}(n-4)\). Position \(Q\) is equivalent to \(\text{DC}(n-4)+*1\) by Proposition 25.
If \(\text{nim}(\text{DC}(n-4))=0\), then \(\text{nim}(P)=1=\text{nim}(Q)\) so that \(\text{nim}(\text{DNT}(W_n))=\text{mex}\{1\}=0\). If \(\text{nim}(\text{DC}(n-4))>0\), then \(\text{nim}(P)=0\) and \(\text{nim}(Q)\ne 1\) so that \(\text{nim}(\text{DNT}(W_n))=\text{mex}\{0,\text{nim}(Q)\}=1\). ◻
28. [17] The sequence of nim-values of \(\text{DC}(n)\) is eventually periodic with preperiod \[\begin{gather} \hat{0}1120311033224\hat{0}5\hat{2}\hat{2}3301130211045\hat{2}74 \\ \hat{0}1120311033224\hat{4}5\hat{5}\hat{2}3301130211045\hat{3}74 \end{gather}\] of length 68 and period \[\hat{8}1120311033224\hat{4}5\hat{5}\hat{9}3301130211045\hat{3}74\] of length 34.
The hats in the previous result indicate where the entries differ. Note that the following theorem is consistent with Proposition 24.
29. For wheel graphs, \[\text{nim}(\text{DNT}(W_n))=\begin{cases} 0, & n \in \{18,38\} \text{ or } n \text{ mod } 34 \in \{8, 12,24,28,32\}\\ 1, & \text{otherwise}. \end{cases}\]
Proof. By Proposition 27, \(\text{nim}(\text{DNT}(W_n))=0\) exactly when \(\text{nim}(\text{DC}(n-4))=0\) and equals \(1\) otherwise. By Proposition 28, \(\text{nim}(\text{DC}(n-4))=0\) exactly in the cases in the statement of the theorem. ◻
The ordinal sum \(\mathsf{G}:\mathsf{H}\) of the gamegraphs \(\mathsf{G}\) and \(\mathsf{H}\) [12], [18], [19] has position set \(\mathsf{G}\times\mathsf{H}\) and \[\text{Opt}(p,q):=\begin{cases} \text{Opt}(p)\times\{q\}, & p\ne p_0 \\ (\text{Opt}(p_0)\times\{q\})\cup(\{p_0\}\times\text{Opt}(q)), & p=p_0, \end{cases}\] where \(p_0\) is the starting position of \(\mathsf{G}\). This means a player can make a move either in \(\mathsf{G}\) or in \(\mathsf{H}\) but \(\mathsf{H}\) is discarded as soon as a move is made in \(\mathsf{G}\).
Example 16. Figure [fig:ordinalProd] shows the gamegraph \(\mathsf{G}\) and the ordinal sum \(*2:\mathsf{G}\). Positions of the form \((p_0,q)=(*2,q)\) in \(*2:\mathsf{G}\) are shown as squares. The arrows between these squares represent moves in \(\mathsf{G}\). The other arrows represent moves in \(*2\).
This example suggests the following.
30. If \(\mathsf{G}\) is a gamegraph, then \(\text{nim}(*k:\mathsf{G})=k+\text{nim}(\mathsf{G})\).
Proof. It is easy to see that \(\text{nim}(*j,p)=j\) for all \(j\in\{0,\ldots,k-1\}\) and \(p\in\mathsf{G}\). Structural induction shows that \[\begin{align} \text{nim}(*k,p) & =\text{mex}(\text{nim}(\text{Opt}(*k)\times\{p\})\cup\text{nim}(\{*k\}\times\text{Opt}(p))) \\ & =\text{mex}(\{\text{nim}(*j,p)\mid *j\in\text{Opt}(*k)\} \cup\{\text{nim}(*k,q)\mid q\in\text{Opt}(p) \}) \\ & =\text{mex}(\{0,\ldots,k-1\}\cup\{k+\text{nim}(q)\mid q\in\text{Opt}(p)\}) \\ & = k+\text{nim}(p). \end{align}\] Hence \(\text{nim}(*k:\mathsf{G})=\text{nim}(*k,p_0)=k+\text{nim}(p_0)=k+\text{nim}(\mathsf{G})\), where \(p_0\) is the starting position of \(\mathsf{G}\). ◻
31. The games \(\text{TER}_{\{v_i\}}(W_n)\) and \(*1:\text{DNT}_{\{v_i\}}(W_n)\) have the same nim-value.
Proof. Identifying the terminal positions in each game creates two isomorphic quotient gamegraphs. The canonical quotient maps are option-preserving and hence nim-value preserving. ◻
Example 17. Figure [fig:mapOrd] shows the gamegraphs for \(\text{TER}_{\{v_i\}}(W_5)\) and \(*1:\text{DNT}_{\{v_i\}}(W_5)\). Vertex \(v_i\) is drawn on top. The two quotient maps identify all the shaded terminal positions.
32. For wheel graphs, \[\text{nim}(\text{TER}(W_n))=\begin{cases} 2, & n \text{ mod } 34 \in \{5, 6,10,11,25,26,30,31\}\\ 1, & \text{otherwise}. \end{cases}\]
Proof. By symmetry, the positions with a single rim vertex selected are essentially the same. So \(a:=\text{nim}(\{v_i\})\) is independent of the choice of \(i\). A position that contains a rim vertex \(v_i\) has nonzero nim-value since the next player can win by marking \(v_{i+1}\). Hence \(a>0\). Also \(\text{nim}(\{c\})=0\) since each option \(\{c,v_i\}\) of \(\{c\}\) has nonzero nim-value. Thus \[\text{nim}(\text{TER}(W_n))=\text{mex}(\text{nim}(\{\{c\},\{v_1\},\ldots,\{v_n-1\}\}))=\text{mex}(\{0,a\})\in\{1,2\},\] as depicted in Figure [fig:WheelTERCases]. In fact, \(\text{nim}(\text{TER}(W_n))\) is \(2\) if \(a=1\) and \(1\) if \(a>1\).
By Propositions 25, 30, and 31, \[a=\text{nim}(\text{TER}_{\{v_i\}}(W_n))=\text{nim}(*1:\text{DNT}_{\{v_i\}}(W_n))=\text{nim}(\text{DC}(n-4)+*1)+1.\] This value is \(1\) exactly when \(\text{nim}(\text{DC}(n-4))=1\). So the result follows from Propositions 28. ◻
5.5 Generalized wheel graphs↩︎
The generalized wheel graph \(W_{m,n}\) with \(m\ge 2\) and \(n\ge 3\) is the join \(\overline{K}_m+C_n\) with \(m+n\) total vertices in \(V(\overline{K}_m)=\{c_1, \ldots, c_m\}\) and \(V(C_n)=\{v_1, \ldots, v_n\}\).
33. For generalized wheel graphs, \[\text{nim}(\text{DNT}(W_{m,3}))=1,\quad \text{nim}(\text{TER}(W_{m,3}))=2.\]
Proof. Since \(C_3\) is isomorphic to \(K_3\), \(W_{m,3}\) is a complete split graph. So the result follows from Proposition 10. ◻
34. For generalized wheel graphs with \(n\ge 4\), \[\mathcal{N}^* = \{ \{c_i, c_j\}^c \mid i \ne j \} \cup \{ \{v_k, v_\ell\}^c \mid \text{k\not=\ell and v_k, v_\ell nonadjacent}\}.\]
Proof. We know from [8] that \[\mathcal{G}^*=\complement(\mathcal{N})=\{\{c_i,v_j,v_{j+1}\}^c\mid i \in \{1,\ldots,m\}, j \in \{1,\ldots,n\}\}.\] It is easy to verify that \[\mathcal{G}=\mathrm{Tr}(\mathcal{G}^*))= \{ \{c_i, c_j\} \mid i \ne j \} \cup \{ \{v_k, v_\ell\} \mid \text{k\not=\ell and v_k, v_\ell nonadjacent}\},\] which proves the claim about \(\mathcal{N}^*=\complement(\mathcal{G})\). ◻
35. For generalized wheel graphs with \(n\ge 4\), \(\text{nim}(\text{DNT}(W_{m,n}))=\text{pty}(V)\).
We now focus on \(\text{TER}(W_{m,n})\) for the rest of the section. We will map this game to another simpler game. To describe this map, we need to introduce some terminology.
A partition \(\lambda\) of a nonnegative integer \(n\) is a multiset of nonnegative integers whose sum is \(n\). It is customary to write the elements of a partition as a nonincreasing list \(\lambda=[l_1,\ldots,l_k]\). We will sometimes use the notation \(\lambda^n\) if we want to emphasize that we have a partition of \(n\). We call each \(\lambda_i\) a part of \(\lambda\). We say that we split \(\lambda\) if we replace a part \(\alpha\) with a pair \(\beta, \gamma \geq 0\) such that \(\beta+\gamma=\alpha-1\). The special split when \(\gamma=0\) is called a decrement.
It will sometimes be useful to write \(\lambda^n_o\) for a partition of \(n\) with exactly \(o\) odd parts. Replacing an even part with an odd and an even part increases the number of odd parts by \(1\). Replacing an odd part with two even parts decreases the number of odd parts by one, whereas replacing an odd part with two odd parts increases the number of odd parts by one. Hence a split of \(\lambda^n_0\) always results in \(\lambda^{n-1}_1\). A split of \(\lambda^n_1\) results in either \(\lambda^{n-1}_0\) or \(\lambda^{n-1}_2\), with the former always being available.
Once a rim vertex has been selected in a position \(P\) of \(\text{TER}(W_{m,n})\), we define \(f(P):=(c,\lambda)\), where \(c\) is the number of unselected central vertices remaining and \(\lambda\) is the partition that describes the sizes of the consecutive clusters of unselected rim vertices. If \(P\) is a terminal position then \(f(P)\) is \((0,[1])\), \((0,[2])\), \((1,[\,])\), \((1,[1])\), or \((1,[2])\). If a rim vertex has not yet been selected, we will use the notation \(\Lambda^n\) to denote all of the original rim vertices, and we define \(f(P_0):=(m,\Lambda^n)\) for the starting position \(P_0\) of \(\text{TER}(W_{m,n})\). We consider \(\Lambda^n\) to be a special partition whose only split is \([n-1]\). We allow \(\lambda^n_{\text{pty}(n)}\) to mean \(\Lambda^n\).
Let \(\text{SPL}(m,n)\) be the game whose set of positions is \(\{f(P)\mid P\in\text{TER}(W_{m,n})\}\). There are two possible moves from position \((c,\lambda)\). A dehub decreases \(c\) by 1. The other option is a split of \(\lambda\). Selecting a central vertex in position \(P\) decreases the first component of \(f(P)\), while selecting a rim vertex creates a split of the second component of \(f(P)\). So \(f:\text{TER}(W_{m,n})\to\text{SPL}(m,n)\) is an option-preserving map. As a consequence of [14], [15], \(\text{nim}(\text{TER}(W_{m,n}))=\text{nim}(\text{SPL}(m,n))\).
Example 18. Figure [fig:fimage] shows a play in \(\text{TER}(W_{2,4})\) and its image in \(\text{SPL}(2,4)\) under the option-preserving map \(f\).
36. As in [10], we are going to describe complicated winning strategies for the second player using case analysis diagrams. A case analysis diagram is a digraph whose vertices are either single positions or sets of positions. Sets of positions are usually described using some parameters and conditions on these parameters. Single headed arrows represent the possible moves for the first player, while double headed arrows represent the winning replies for the second player. The diagram may contain cycles. The second player breaks out of these cycles along moves represented by dashed arrows when these moves become available. This is guaranteed since the game does not have infinite plays. A sink vertex is either a terminal position of the game or a nonterminal position that has already been proved to be a losing position. The latter is indicated by \(*0\) or a reference to another case analysis diagram. These sink vertices only have double headed incoming arrows. The starting position of the strategy is usually on the top of the diagram but a diagram can have several starting positions indicated by \(\begin{tikzpicture} \node[draw,circle,red,inner sep=.7] {\scriptscriptstyle i}; \end{tikzpicture}\) symbols for some number \(i\). Notation such as (X.\(i\)) indicates that the diagram continues at starting point \(\begin{tikzpicture} \node[draw,circle,red,inner sep=.7] {\scriptscriptstyle i}; \end{tikzpicture}\) of Diagram (X). Occasionally, a \(\bullet\) indicates a position after the first player’s move for which a description is not necessary.
We demonstrate the use of case analysis diagrams with a familiar game.
Example 19. Figure [fig:nplusn] shows a case analysis diagram for a strategy of the second player to win \(*n+*n\). Play starts at
if \(n>1\) and at
if \(n=0\). A dashed arrow becomes available for the second player when the first player moves to a position that makes \(a=0\).
Lemma 1. Position \((3,[3])\) of \(\text{SPL}\) has nim-value \(1\).
Proof. The case analysis diagram in Figure [fig:Case3nnEndgame3] shows a winning strategy for the second player starting at \(\begin{tikzpicture} \node[draw,circle,red,inner sep=.7] {\scriptscriptstyle 1}; \end{tikzpicture}\). ◻
![Figure 14: Case analysis diagram (A) for one possible endgame. The alternate starting positions \begin{tikzpicture}
\node[draw,circle,red,inner sep=.7] {\scriptscriptstyle 2};
\end{tikzpicture} and \begin{tikzpicture}
\node[draw,circle,red,inner sep=.7] {\scriptscriptstyle 3};
\end{tikzpicture} will be needed later in the paper.](/article/2606.05483/_pdflatex/bxyadugc.png "fig:")
Lemma 2. A position \((c,[1^c])\) of \(\text{SPL}\) with \(c\ge 1\) has nim-value \(0\).
Proof. The second player can win by splitting whenever the first player decreases and decreasing whenever the first player splits. ◻
Lemma 3. A position \((c,\lambda^{2l}_0)\) of \(\text{SPL}\) with \(c\in\{0,2\}\) and \(l\geq 2\) has nim-value \(0\).
Proof. A winning strategy for the second player is described in Figure [fig:EvenLemma]. For \(l=2\), the strategy starts at \((0,[4])\), \((0,[2,2])\), \((2,[4])\), or \((2,[2,2])\). For \(l \geq 3\), the starting position is at
or
. Note that the possible partitions described as \(\lambda_1^5\) are \([5]\), \([4,1]\), \([3,2]\), and \([2,2,1]\). From each of these either \([4]\) or \([2,2]\) is available after a split, indicated by a dashed arrow in the diagram. ◻
![Figure 15: Case analysis diagram (B) for a strategy with k\ge 3. Here, (i,4) stands for either (i,\Lambda^4) or (i,[4]) with i \in \{0,1,2\}. Arrow colors distinguish between dehub and split moves.](/article/2606.05483/_pdflatex/wsbfajqg.png "fig:")
We say that a partition \(\lambda:=[l_1,l_2,\ldots,l_k]\) is solid if \(l_1 \geq 4\) or \(l_2 \geq 2\). We will write \(\boldsymbol{\lambda}\) to indicate a solid partition. If \(\lambda\) is not solid, then \(\lambda\) must have the form \([1^a]\), \([2,1^a]\), or \([3,1^a]\) for some \(a \geq 0\). It is impossible to split a solid partition into a partition of the form \([1^a]\). We will also consider \(\Lambda^n\) to be solid for all \(n \geq 5\).
Lemma 4. A solid partition \(\boldsymbol{\lambda}\) different from \([4]\) and \([2,2]\) can be split into a solid partition.
Proof. If \(\boldsymbol{\lambda}=\Lambda^n\), then \(n\ge 5\) and so the only split \([n-1]\) is solid. Thus, we may assume that \(\boldsymbol{\lambda}=[l_1,l_2,\ldots,l_k]\). If \(l_1>4\), then we can decrement \(l_1\). If \(l_1=4\), then \(l_2\in\{1,2,3,4\}\) since \(\lambda \not= [4]\), so we can decrement \(l_2\). If \(l_1=3\), then \(l_2\in\{2,3\}\), so we can decrement \(l_1\). Finally, if \(l_1=2\), then \(l_2=2\) and \(l_3 >0\) since \(\lambda \not=[2,2]\), so we can decrement \(l_3\). ◻
Lemma 5. A partition \(\lambda_o^c\) with \(o\le 2\) and \(c\ge 5\) is solid.
Proof. For a contradiction suppose that \(\lambda_o^c\) is not solid. Then \(\lambda_o^c\) must be \([1^a]\), \([2,1^a]\), or \([3,1^a]\) for some \(a\). Since \(c\ge 5\), we must have \(a\ge 2\). This implies the contradiction \(o\ge 3\). ◻
Lemma 6. A position \((c,\boldsymbol{\lambda}^{c+2})\) of \(\text{SPL}\) with \(c\ge 3\) has nim-value \(0\).
Proof. A winning strategy for the second player is described in Figure [fig:GenWheelPhase2]. The dotted arrow is justified by Lemma 4. We also use the fact that it is impossible to split a solid partition to \([1^a]\). Positions \((2,[4])\) and \((2,[2,2])\) are losing by Lemma 3. Position \((c,[1^c])\) is losing by Lemma 2. Note that the strategy works even if \(\lambda_0^{c+2}=\Lambda^{c+2}\). ◻
Lemma 7. A position \((c+(2k+3),\lambda^{c})\) of \(\text{SPL}\) with \(c, k\ge 0\) has nim-value \(0\).
Proof. The second player can win by splitting whenever possible until position \((3,[\,])\) is reached, as shown in Figure [fig46split]. This is a losing position as shown in Figure [fig:Case3nnEndgame3]. ◻
37. For generalized wheel graphs with \(n \geq 4\), \[\text{nim}(\text{TER}(W_{m,n}))=\begin{cases} 0, & n+m \text{ even and } 2\le d\\ 0, & n+m \text{ odd and } d \leq 0\\ 1, & n+m \text{ even and } d \leq 0\\ 1, & n+m \text{ odd and } 2\le d\\ 2, & d=1, \end{cases}\] where \(d:=n-m\).
Proof. It is sufficient to prove the corresponding result for \(\text{SPL}(m,n)\) due to the option-preserving map \(f\). We consider the five cases of our formula separately. In each case we show that the second player can win.
Case 1. \(\text{pty}(n+m)=0\) and \(m+2\le n\): The second player’s goal is to keep the unselected central and rim vertices even in a careful way until there are only two central vertices left or there are exactly two more rim than central vertices. Figure [fig:Case1Phase1BeginningNew] shows a case analysis diagram for a winning strategy. Position \((2,\lambda_0^{2+2k})\) is losing by Lemma 3. Lemma 5 implies that \({\boldsymbol{\lambda}_0^{e+2}}\) is solid, so \((e,{\boldsymbol{\lambda}}_0^{e+2})\) is losing by Lemma 6.
Case 2. \(\text{pty}(n+m)=1\) and \(m>n\): If \(m\geq n+3\), then the second player wins by Lemma 7. Otherwise, \(m=n+1\) and the second player wins using the strategy shown in Figure [fig:Case2].
Case 3. \(\text{pty}(n+m)=0\) and \(m\geq n \geq 4\): We show that the second player can win \(\text{SPL}(m,n)+*1\). If the first player splits or makes a move in \(*1\), then the second player can move to \((m,[n-1])\). Since \(m \geq n-1\) and \(m+(n-1)\) is odd, this is a losing position by Case 2.
So we may assume that the first player initially moves to \((m-1,\Lambda^n)+*1\). If \(m \geq n+2\), then the second player can move to \((m-1,\Lambda^n)\) and follow the strategy from Case 2.
So we may also assume that \(m=n\) and the first player moves to \((n-1,\Lambda^n)+*1\). Then the second player can move to \((n-1,[n-1])+*1\) and win following the strategy in Figure [fig:Case3nnEndgame2]. The continuation from \((3,[3])+*1\) is shown in Figure [fig:Case3nnEndgame3]. Positions \((o,[o-1])\), \((e,\lambda^{e-1}_1)\), and \((o,\lambda^{o-3})\) are losing as shown in Figure [fig:Case2].
![Figure 20: Case analysis diagram (G) for the endgame of Case 3 starting at either (o,[o])+*1 or (e,[e])+*1 for some odd o \geq 5 or even e \geq 4.](/article/2606.05483/_pdflatex/skuqbnvc.png "fig:")
Case 4. \(\text{pty}(n+m)=1\) and \(m+2 \leq n\): We will show that the second player can win \(\text{SPL}(m,n)+*1\). First suppose that \(m=2\) and the first player initially moves to \((1,\Lambda^n)+*1\). The second player then can move in \(*1\) to get to \((0,[n-1])\) at the fourth move of the game. Since \(n \geq m+2=4\) and \(n\) is odd, \(n-1\) is even and at least \(4\). Hence the second player can win by Lemma 3.
Now suppose that \(m>2\) or the first player’s initial selection is a split. The second player can move to either \((m-1,\Lambda^n)\) where \(m-1 \geq 2\) or \((m,[n-1])\) where \(m \geq 2\). The second player now wins as in Case 1 since \(\text{pty}(n+m-1)=0\).
Case 5. \(m+1=n\): The options of the starting position of \(\text{SPL}(m,m+1)\) are \((m-1,\Lambda^{m+1})\) and \((m,[m])\). The former is isomorphic to \(\text{SPL}(m-1,m+1)\) and has nim-value \(*0\) by Case 1 since \((m-1)+(m+1)=2m\) is even and \(m \geq 3\). The latter has nim-value \(*1\) by Figure [fig:Case3nnEndgame2].
Therefore, the nim-value for Case 5 is \(2\). ◻
Recall that the case \(W_{m,3}\) was handled in Proposition 33.
6 Further directions↩︎
Determine whether Conjecture 15 is true. The difficulty is that there is no obvious pairing strategy for the second player due to there being an odd number of vertices.
Sometimes the geodetic closure agrees with the convex hull, but not always. For example, they are not the same on \(Q_n\) if \(n\ge 3\). What are the nim-values for the variations using geodetic closures instead of convex hulls?
The nim-value of an arbitrary hypergraph game can be any integer as shown in [9]. The available nim-values for generating groups is much more limited [20]. What is the spectrum of nim-values for each of the convex hull removing games?
One can study the convex hull hypergraph games on other finite combinatorial objects where there is a natural notion of geodesic. The objects include hypergraphs, weighted graphs, and directed graphs such as the Hasse diagram of a poset and the Cayley digraph for a group.
A case analysis diagram is essentially a quotient of a winning strategy, which is a pruned game digraph containing only the winning moves of the winner. It might be beneficial to develop a formal theory of these quotients similar to [14], [15], [21].
Acknowledgments↩︎
This material is based upon work supported by the National Science Foundation under Grant No. DMS-1929284 while the authors were in residence at the Institute for Computational and Experimental Research in Mathematics (ICERM) in Providence, RI, via the Collaborate@ICERM program.
References↩︎
Date: //↩︎