Nimber Sequences of Node-Kayles Games

Sierra Brown Department of Mathematics

Creighton University 2500 California Plaza Omaha, NE 68178

USA

sierrabrown@creighton.edu

Eugene Fiorini Department of Mathematics

Muhlenberg College 2400 Chew Street Allentown, PA 18104

USA

eugenefiorini@muhlenberg.edu

Diego Manzano-Ruiz Department of Mathematics

Kutztown University of Pennsylvania 15200 Kutztown Road Kutztown, PA 19530

USA

dmanz394@live.kutztown.edu

Riley Waechter

Department of Mathematics and Statistics Northern Arizona University 801 South Osborne Drive

Flagstaff, AZ 86011

USA

rsw66@nau.edu

Spencer Daugherty Department of Mathematics and Statistics Mount Holyoke College 50 College Street South Hadley, MA 01075 USA

                          daugh22s@mtholyoke.edu

Barbara Maldonado Department of Mathematics University of Houston 3507 Cullen Boulevard Houston, TX 77204 USA

                      barbara.maldonado23230@gmail.com

Sean Rainville Department of Mathematics Plymouth State University 17 High Street Plymouth, NH 03264 USA

                           ser1008@plymouth.edu

Tony W. H. Wong Department of Mathematics Kutztown University of Pennsylvania 15200 Kutztown Road Kutztown, PA 19530 USA

                             wong@kutztown.edu

Abstract

Node-Kayles is an impartial game played on a simple graph. The Sprague-Grundy theorem states that every impartial game is associated with a nonnegative integer value called a Nimber. This paper studies the Nimber sequences of various families of graphs, including 3-paths, lattice graphs, prism graphs, chained cliques, linked cliques, linked cycles, linked diamonds, hypercubes, and generalized Petersen graphs. For most of these families, we determine an explicit formula or a recursion on their Nimber sequences.

1 Introduction

An impartial game is a combinatorial two-player game with complete information, in which the allowable moves from any position are identical for both players. One of the classical examples is the game of Nim. The Sprague-Grundy theorem [1] states that all impartial games can be analyzed by assigning a nonnegative integer value, often called the Grundy number or the Nimber, to each game position recursively. According to this theorem, the Nimber of a game is 0 if and only if the game is second-player winning, i.e., the second player has a winning strategy regardless of the moves of the first player. Readers may refer to Winning Ways for Your Mathematical Plays: Volume 1 [2] for more information on impartial games.

Node-Kayles, also known as the domination game [3], is an impartial game played on a simple graph G. Players move alternately. A move involves removing a vertex v, its neighbors N_{G}(v), and all edges incident to all vertices in {v} ∪ N_{G}(v) from G. The first player unable to make a legal move loses the game. In the rest of this article, we let N_{G}[v] denote {v}∪N_{G}(v), the closed neighborhood of v. Furthermore, we let G_{v} denote the residue subgraph G − N_{G}[v]. Since Node-Kayles is an impartial game, we can assign a Nimber to every simple graph G, denoted by G(G). If G = ∅ is an empty graph, then the Node-Kayles game on ∅ is second-player winning, since the first player loses by having no legal move. Hence, G(∅) = 0. For any simple graph G, the Nimber of the Node-Kayles game on G is given by

G(G) = mex{G(G_{v}) : v ∈ V (G)},

where mex represents the “minimal-excluded rule”: if S is a finite subset of ℕ ∪ {0}, then

mex(S) = min{ℕ ∪ {0} \ S}.

Furthermore, if G is a disjoint union of two simple graphs H and K, then

G(G) = G(H) ⊕ G(K),

where x ⊕ y denotes the bitwise XOR between two nonnegative integers x and y.

Nimbers will be our main tool in studying Node-Kayles in this paper. In order to familiarize ourselves with this main tool, let us consider a few simple graphs and compute their respective Nimbers. Let P_{n} denote a path with n vertices. Since P_{1} has only one vertex v, we have (P_{1})_{v} = ∅, and

G(P_{1}) = mex{G((P_{1})_{v})} = mex{G(∅)} = mex{0} = 1.

Since P_{2} has only one edge that connects two vertices u and v, we have (P_{2})_{u} = (P_{2})_{v} = ∅, and hence

G(P_{2}) = mex{G(∅)} = 1.

If G is a graph given by Figure 1, then as seen in Figure 2, the residue subgraphs G_{v_{1}}, G_{v_{3}}, and G_{v_{4}} are isomorphic to P_{2}, while the residue subgraphs G_{v_{2}} and G_{v_{5}} are isomorphic to P_{1}.

\begin{matrix}v_{4} \\ v_{3} \\ v_{2} \\ v_{5} \\ v_{1} \end{matrix}

Figure 1: A simple graph G

\begin{matrix}G_{v_{1}} \\ G_{v_{2}} \\ G_{v_{3}} \\ G_{v_{4}} \\ G_{v_{5}} \\ v_{4} \\ v_{3} \\ v_{4} \\ v_{5} \\ v_{1} \\ v_{1} \\ v_{2} \\ v_{3} \end{matrix}

Figure 2: The residue subgraphs G_{v_{1}}, G_{v_{2}}, G_{v_{3}}, G_{v_{4}}, and G_{v_{5}}

Therefore,

G(G) = mex{G(G_{v_{i}}) : i = 1, 2, 3, 4, 5} = mex{G(P_{1}), G(P_{2})} = mex{1, 1} = 0.

Node-Kayles is a generalization of the game of Kayles. Some sources trace the origin of the game of Kayles to the old Dutch game of Kugelspiel [6, p. 232], played with thirteen bowling pins placed in a row, while other sources trace the origin to the French game of quilles [4, pp. 118, 220]. Nevertheless, both versions agree on the rules of the game. In the game of Kayles, players alternately bowled, knocking down one pin or two neighboring pins with each throw. The objective of the game was to see who could knock down the last standing pin. Notice that this game is not equivalent to the Node-Kayles on a path; rather, in Section 4, we will prove that the game of Kayles is equivalent to the game of Node-Kayles on “n-linked cliques”. Although there is no documented proof on the historical development of the game of Node-Kayles, Simon P. Norton claimed the invention of this game during a personal encounter with the last author of this paper.

There has been literature studying the game of Node-Kayles [5]. Our goal in this paper is to determine the sequence of Nimbers for Node-Kayles on various infinite families of simple graphs. In particular, if (G_{n} : n ∈ ℕ) is a sequence of graphs indexed by natural numbers, then we can define a corresponding Nimber sequence (G(G_{n}) : n ∈ ℕ). To that end, we begin with paths and their derivatives in Section 2. We then present results on lattice graphs of various sizes in Section 3, and apply the results on prism graphs. Section 4 contains results on chained and linked cliques, while Section 5 studies linked cycles and diamonds. Finally, we present results on other graphs such as hypercubes and generalized Petersen graphs in Section 6.

2 Node-Kayles on paths and their derivatives

When we consider an infinite sequence of simple graphs, paths are naturally the first such family that comes to mind. Node-Kayles on paths is well-studied in the literature as the octal game ·137. An octal game is an impartial take-and-break game that involves removing beans from heaps of beans [2]. Each octal game has a specific octal code

·d_{1}d_{2}d_{3} …,

which specifies the set of permissible moves in the take-and-break game. In this code, the k-th digit d_{k} is the sum of a (possibly empty) subset of {1, 2, 4}, where

• 1 indicates a heap can be completely removed by removing k beans;

• 2 indicates a heap can be reduced into a smaller positive size by removing k beans; and

• 4 indicates a heap can be split into two heaps of smaller positive sizes by removing k beans.

For example, an octal game ·137 has d_{1} = 1, d_{2} = 3, and d_{3} = 7, and the code indicates that one can remove one bean from a heap to completely remove that heap; remove two beans from a heap to completely remove that heap or reduce the size of that heap; or remove three beans from a heap to completely remove that heap, reduce the size of that heap, or split that heap into two smaller heaps.

We can now see why Node-Kayles on a path P_{n} is equivalent to an octal game ·137. Recall that each Node-Kayles move requires us to remove a vertex v together with its neighbors N(v); and after each move, the resulting residue subgraph is a forest, where each connected component is a path of the form P_{j} = v_{1}v_{2} ⋯ v_{j} for some positive integer j. Translating to octal games, a connected component P_{j} is analogous to a heap of j beans. The only way to remove exactly one vertex from P_{j} is when j = 1, thus completely removing the component. Therefore, d_{1} = 1. There are two ways to remove two vertices from P_{j}: we can either completely remove this component when j = 2, or reduce the length of this path by removing the closed neighborhoods N_{(P_{j})}[v_{1}] or N_{(P_{j})}[v_{j}] when j ≥ 3. Therefore, d_{2} = 1 + 2 = 3. There are three ways to remove three vertices from P_{j}: we can completely remove this component when j = 3, reduce the length of this path by removing N_{P_{j}}[v_{2}] or N_{P_{j}}[v_{j−1}] when j ≥ 4, or split P_{j} into two shorter paths by removing N_{P_{j}}[v_{i}], 3 ≤ i ≤ j − 2, when j ≥ 5. Therefore, d_{3} = 1 + 2 + 4 = 7. Due to this equivalence, the Nimber sequence (G(P_{n}) : n ∈ ℕ) of paths is the same as the Nimber sequence of the octal game ·137, which appears on the On-Line Encyclopedia of Integer Sequences (OEIS) as \underline{A002187} [7].

Recall that for each positive integer m, the m-th power G^{m} of a simple graph G is a new graph on the same vertex set such that two vertices are adjacent in G^{m} if and only if their distance in G is at most m. It is not difficult to see that Node-Kayles on the square (P_{n})^{2} and the cube (P_{n})^{3} of a path are equivalent to octal games ·11337 and ·1113337, respectively. Hence, the Nimber sequences (G((P_{n})^{2}) : n ∈ ℕ) and (G((P_{n})^{3}) : n ∈ ℕ) are also known, and they appear on the OEIS as \underline{A071426} and \underline{A071441} [7], respectively.

We can, of course, continue to explore the Nimber sequence (G((P_{n})^{m}) : n ∈ ℕ) when m ∈ {4, 5, … }. Instead, we study a variation of the power of paths. Define an m-path P_{n}(m) as a path P_{n} = v_{1}v_{2} ⋯ v_{n} with additional edges {v_{i}v_{j} : |i − j| = m}. In this section, we determine the Nimber sequence (G(P_{n}(3)) : n ∈ ℕ) of 3-paths.

To achieve this, we need to further define two related families of graphs. A B-version of a 3-path, denoted by P_{n}^{B}(3), is a 3-path P_{n}(3) with an additional vertex v_{−1}, and if n ≥ 2, an additional edge v_{−1}v_{2}. A C-version of a 3-path, denoted by P_{n}^{C}(3), is a B-version of a 3-path P_{n}^{B}(3) with an additional vertex v_{n+2}, and if n ≥ 2, an additional edge v_{n−1}v_{n+2}. Figures 3 to 5 are examples of a 3-path, a B-version of a 3-path, and a C-version of a 3-path, respectively.

\begin{matrix}v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ v_{6} \\ v_{7} \\ v_{8} \\ v_{9} \\ v_{10} \end{matrix}

Figure 3: The 3-graph P_{10}(3)

\begin{matrix}v_{−1} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ v_{6} \\ v_{7} \\ v_{8} \end{matrix}

Figure 4: The B-version of a 3-path P_{8}^{B}(3)

\begin{matrix}v_{−1} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ v_{6} \\ v_{7} \\ v_{8} \\ v_{10} \end{matrix}

Figure 5: The C-version of a 3-path P_{8}^{C}(3)

To simplify the notation, we define A(n) = G(P_{n}(3)), B(n) = G(P_{n}^{B}(3)), and C(n) = G(P_{n}^{C}(3)). The sequence (A(n) : n ∈ ℕ) is now listed on the OEIS as \underline{A317367} [7].

Theorem 1. The Nimber sequences (A(n) : n ≥ 116), (B(n) : n ≥ 117), and (C(n) : n ≥ 118) are periodic with period 62.

Proof. By definition,

C(n) = mex{G(P_{n}^{C}(3)_{v_{i}}) : i = −1, 1, 2, …, n, n + 2}.

By the symmetry of P_{n}^{C}(3), we have

C(n) = mex{G(P_{n}^{C}(3)_{v_{i}}) : i = −1, 1, 2, …, ⌈n/2⌉}.

It is easy to see that P_{n}^{C}(3)_{v_{−1}} has v_{−1} and v_{2} removed, so G(P_{n}^{C}(3)_{v_{−1}}) = C(n−2). Similarly, we can easily see that G(P_{n}^{C}(3)_{v_{i}}) = C(i − 4) ⊕ C(n − i − 3) for 5 ≤ i ≤ ⌈n/2⌉. To compute G(P_{n}^{C}(3)_{v_{i}}) for 1 ≤ i ≤ 4, it is convenient to extend the definition of P_{n}^{C}(3) to cases when −3 ≤ n ≤ 0 and determine the corresponding C(n) as follows.

n  P_{n}^{C}(3)  C(n)
−3  1
−2 ∅ 0
−1  0
0  1

In this way, we find the recursion

C(n) = mex ({C(n − 2)} ∪ {C(i − 4) ⊕ C(n − i − 3) : 1 ≤ i ≤ ⌈n/2⌉})  (1)

for all n ∈ ℕ. Now, we are ready to prove that (C(n) : n ≥ 118) is periodic with period 62 by strong induction.

With recursion (1), together with the initial conditions (C(−3), C(−2), C(−1), C(0)) = (1, 0, 0, 1), we can compute the values of the sequence (C(n) : 1 ≤ n ≤ 427), which is periodic with period 62 when 118 ≤ n ≤ 427. Assume that for some n ≥ 428, C(i) = C(i − 62) for all 180 ≤ i < n. Then

C(n) = mex ({C(n − 2)} ∪ {C(i − 4) ⊕ C(n − i − 3) : 1 ≤ i ≤ ⌈n/2⌉ − 31}
∪ {C(i − 4) ⊕ C(n − i − 3) : ⌈n/2⌉ − 30 ≤ i ≤ ⌈n/2⌉})

= mex ({C((n − 62) − 2)} ∪ {C(i − 4) ⊕ C((n − 62) − i − 3) : 1 ≤ i ≤ ⌈(n − 62)/2⌉}

∪ {C(i − 4) ⊕ C((n − 62) − i − 3) : ⌈n/2⌉ − 30 ≤ i ≤ ⌈n/2⌉})

= mex ({C((n − 62) − 2)} ∪ {C(i − 4) ⊕ C((n − 62) − i − 3) : 1 ≤ i ≤ ⌈(n − 62)/2⌉}

∪ {C(i − 4) ⊕ C((n − 62) − i − 3) : ⌈n/2⌉ − 92 ≤ i ≤ ⌈n/2⌉ − 62})

= mex ({C((n − 62) − 2)} ∪ {C(i − 4) ⊕ C((n − 62) − i − 3) : 1 ≤ i ≤ ⌈(n − 62)/2⌉})

= C(n − 62),

which completes our induction.

Next, we study B(n). By definition,

B(n) = mex{G(P_{n}^{B}(3)_{v_{i}}) : i = −1, 1, 2, …, n}.

Similar to the study of C(n), we have G(P_{n}^{B}(3)_{v_{−1}}) = B(n − 2), and G(P_{n}^{B}(3)_{v_{i}}) = C(i − 4) ⊕ B(n − i − 3) for 1 ≤ i ≤ n − 4. Again, it is convenient to extend the definition of P_{n}^{B}(3) to cases when −3 ≤ n ≤ 0 and determine the corresponding B(n) as follows.

n P_{n}^{B}(3) B(n)
−3  ∅  0
−2  ∅  0
−1  1
0  1

In this way, we find the recursion

B(n) = mex ({B(n − 2)} ∪ {C(i − 4) ⊕ B(n − i − 3) : 1 ≤ i ≤ n})  (2)

for all n ∈ ℕ. Again, we will prove that (B(n) : n ≥ 117) is periodic with period 62 by strong induction.

With recursion (2), together with the initial conditions (B(−3), B(−2), B(−1), B(0)) = (0, 0, 1, 1) and the sequence (C(n) : n ∈ ℕ), we can compute the values of the sequence (B(n) : 1 ≤ n ≤ 364), which is periodic with period 62 when 117 ≤ n ≤ 364. Assume that for some n ≥ 365, B(i) = B(i − 62) for all 179 ≤ i < n. Then

B(n) = mex ({B(n − 2)} ∪ {C(i − 4) ⊕ B(n − i − 3) : 1 ≤ i ≤ n − 182}
∪ {C(i − 4) ⊕ B(n − i − 3) : n − 181 ≤ i ≤ n})

= mex ({B((n − 62) − 2)} ∪ {C(i − 4) ⊕ B((n − 62) − i − 3) : 1 ≤ i ≤ n − 182}

∪ {C(i − 4) ⊕ B((n − 62) − i − 3) : n − 243 ≤ i ≤ n − 62})

= mex ({B((n − 62) − 2)} ∪ {C(i − 4) ⊕ B((n − 62) − i − 3) : 1 ≤ i ≤ n − 62})

= B(n − 62),

which completes our induction.

Finally, we study A(n). By definition,

A(n) = mex{G(P_{n}(3)_{v_{i}}) : i = 1, 2, …, n}.

By the symmetry of P_{n}(3), we have

A(n) = mex{G(P_{n}(3)_{v_{i}}) : i = 1, 2, …, ⌈n/2⌉}.

Similar to the study of B(n) and C(n), we have G(P_{n}(3)_{v_{i}}) = B(i − 4) ⊕ B(n − i − 3) for 1 ≤ i ≤ ⌈n/2⌉. Hence, we find the recursion

A(n) = mex ({B(i − 4) ⊕ B(n − i − 3) : 1 ≤ i ≤ ⌈n/2⌉})  (3)

for all n ∈ ℕ. Once again, we will prove that (A(n) : n ≥ 116) is periodic with period 62 by strong induction.

With recursion (3), together with the sequence (B(n) : n ∈ ℕ), we can compute the values of the sequence (A(n) : 1 ≤ n ≤ 424), which is periodic with period 62 when 116 ≤ n ≤ 424. Assume that for some n ≥ 425, A(i) = A(i − 62) for all 178 ≤ i < n. Then

A(n) = mex ({B(i − 4) ⊕ B(n − i − 3) : 1 ≤ i ≤ ⌈n/2⌉ − 31}
∪ {B(i − 4) ⊕ B(n − i − 3) : ⌈n/2⌉ − 30 ≤ i ≤ ⌈n/2⌉})
= mex ({B(i − 4) ⊕ B((n − 62) − i − 3) : 1 ≤ i ≤ ⌈(n − 62)/2⌉}
∪ {B(i − 4) ⊕ B((n − 62) − i − 3) : ⌈n/2⌉ − 92 ≤ i ≤ ⌈n/2⌉ − 62})
= mex ({B(i − 4) ⊕ B((n − 62) − i − 3) : 1 ≤ i ≤ ⌈(n − 62)/2⌉})
= A(n − 62),

which completes our induction.

By computation, we further discover that the sequences (A(n) : n ≥ 50), (B(n) : n ≥ 51), and (C(n) : n ≥ 52) are identical, and their repeating unit (A(n) : 116 ≤ n ≤ 177) is given by

6, 4, 7, 5, 8, 4, 1, 1, 0, 2, 1, 3, 0, 2, 1, 3, 0, 1, 1, 3, 0, 2, 3, 3, 2, 2, 7, 4, 6, 5, 4, 4, 5, 5, 7, 9, 6, 3, 3, 2, 0, 3, 1, 1, 0, 3, 1, 2, 0, 3, 1, 2, 0, 1, 1, 4, 0, 5, 5, 4, 7, 5.

In particular, the maximum Nimber value is 9, occurring at A(151 + 62k) for all nonnegative integers k. Also, when n ∈ ℕ, A(n) = 0 if and only if

n ∈ {22, 58} or n ≡ 0, 4, 8, 12, 32, 36, 40, 44, or 48 (mod 62).

Unlike Node-Kayles on the powers of a path, Node-Kayles on a 3-path is not an octal game. Nonetheless, the Nimber sequence (A(n) : n ∈ ℕ) for 3-paths is almost identical to that of the octal game ·124, listed on the OEIS as \underline{A071461} [7]. In fact, the two sequences are different at only two positions, namely G(P_{21}(3)) and G(P_{49}(3)). Such level of resemblance seems to indicate some deeper relationship hidden behind the two games.

It is worth noting that the recursions of the three different Nimber sequences, given by equations (1), (2), and (3), are the key to the proof of periodicity of (A(n) : n ≥ 116). Similar techniques are also employed in subsequent sections.

3 Lattice graphs and prism graphs

Apart from the powers of paths, lattice graphs are another natural generalization of paths. In this section, we study the Nimber sequences of some lattice graphs. Define an n×m lattice L_{n×m} as the Cartesian product P_{n}□P_{m} with the vertex set {v_{i,j} : 1 ≤ i ≤ n, 1 ≤ j ≤ m} and the edge set {v_{i,j}v_{i′,j′} : |i − i′| + |j − j′| = 1}. In particular, L_{n×2} is a ladder graph with n “rungs.”

To determine the Nimber sequence (G(L_{n×2}) : n ∈ ℕ) of ladder graphs, we need to further define three related families of graphs. The first variation, denoted by L_{n×2}^{−}, is a ladder graph L_{n×2} with an additional vertex v_{n+1,2} and an additional edge v_{n,2}v_{n+1,2}; the second variation, denoted by ^{−}L_{n×2}^{−}, is the first variation L_{n×2}^{−} with an additional vertex v_{0,2} and an additional edge v_{0,2}v_{1,2}; and the third variation, dented by _{−}L_{n×2}^{−}, is the first variation L_{n×2}^{−} with an additional vertex v_{0,1} and an additional edge v_{0,1}v_{1,1}. Figures 6 to 9 are examples of a ladder graph, its first variation, second variation, and third variation, respectively.

\begin{matrix}v_{1,1} \\ v_{1,2} \\ v_{2,1} \\ v_{2,2} \\ v_{3,1} \\ v_{3,2} \\ v_{4,1} \\ v_{4,2} \\ v_{5,1} \\ v_{5,2} \\ v_{6,1} \\ v_{6,2} \\ v_{7,1} \\ v_{7,2} \\ v_{8,1} \\ v_{8,2} \end{matrix}

Figure 6: The lattice graph L_{8×2}

\begin{matrix}v_{1,1} \\ v_{1,2} \\ v_{2,1} \\ v_{2,2} \\ v_{3,1} \\ v_{3,2} \\ v_{4,1} \\ v_{4,2} \\ v_{5,1} \\ v_{5,2} \\ v_{6,1} \\ v_{6,2} \\ v_{7,1} \\ v_{7,2} \\ v_{8,1} \\ v_{8,2} \\ v_{9,2} \end{matrix}

Figure 7: The first variation of the lattice graph L_{8×2}^{−}

\begin{matrix}v_{1,1} \\ v_{1,2} \\ v_{2,1} \\ v_{2,2} \\ v_{3,1} \\ v_{3,2} \\ v_{4,1} \\ v_{4,2} \\ v_{5,1} \\ v_{5,2} \\ v_{6,1} \\ v_{6,2} \\ v_{7,1} \\ v_{7,2} \\ v_{8,1} \\ v_{8,2} \\ v_{9,2} \\ v_{0,2} \end{matrix}

Figure 8: The second variation of the lattice graph ^{−}L_{8×2}^{−}

\begin{matrix}v_{1,1} \\ v_{1,2} \\ v_{2,1} \\ v_{2,2} \\ v_{3,1} \\ v_{3,2} \\ v_{4,1} \\ v_{4,2} \\ v_{5,1} \\ v_{5,2} \\ v_{6,1} \\ v_{6,2} \\ v_{7,1} \\ v_{7,2} \\ v_{8,1} \\ v_{8,2} \\ v_{9,2} \\ v_{0,1} \end{matrix}

Figure 9: The third variation of the lattice graph _{−}L_{8×2}^{−}

Theorem 2. The Nimber sequences (G(L_{n×2}) : n ∈ ℕ), (G(L_{n×2}^{−}) : n ∈ ℕ), (G(^{−}L_{n×2}^{−}) : n ∈ ℕ), and (G(_{−}L_{n×2}^{−}) : n ∈ ℕ) are given by the following:

G(L_{n×2}) = \begin{cases}1, & if n is odd; \\ 0, & otherwise. \end{cases}

and

G(L_{n×2}^{−}) = n + 1, G(^{−}L_{n×2}^{−}) = 1, and G(_{−}L_{n×2}^{−}) = 0

for all n ∈ ℕ.

Proof. First, note that L_{1×2}, L_{1×2}^{−}, and _{−}L_{1×2}^{−} are isomorphic to paths P_{2}, P_{3}, and P_{4}, respectively, so G(L_{1×2}) = G(P_{2}) = 1, G(L_{1×2}^{−}) = G(P_{3}) = 2, and G(_{−}L_{1×2}^{−}) = G(P_{4}) = 0 from the Nimber sequence of the octal game ·137. We can also easily see that G(^{−}L_{1×2}^{−}) = mex{1 ⊕ 1, 0} = mex{0, 0} = 1. Hence, the base cases for our strong induction are true.

Before we proceed with our induction proof, it is convenient to extend the definitions of L_{n×2}^{−}, ^{−}L_{n×2}^{−}, and _{−}L_{n×2}^{−} to cases when −1 ≤ n ≤ 0 and determine the corresponding Nimbers as follows.

n L_{n×2}^{−} G(L_{n×2}^{−}) ^{−}L_{n×2}^{−} G(^{−}L_{n×2}^{−}) _{−}L_{n×2}^{−} G(_{−}L_{n×2}^{−})
−1 ∅ 0 = n + 1  1  ∅  0
0  1 = n + 1  1  0

Now, we are ready to finish our proof by strong induction. Assume that for some integer n ≥ 2,

G(L_{i×2}^{−}) = i + 1, G(^{−}L_{i×2}^{−}) = 1, and G(_{−}L_{i×2}^{−}) = 0

for all integers −1 ≤ i < n. To find G(L_{n×2}), we exhaust all possible first moves in the Node-Kayles game on L_{n×2}. For each 1 ≤ i ≤ n,

G((L_{n×2})_{v_{i,1}}) = G((L_{n×2})_{v_{i,2}}) = G(L_{(i−2)×2}^{−}) ⊕ G(L_{(n−i−1)×2}^{−}) = (i − 1) ⊕ (n − i).

Note that (i − 1) ⊕ (n − i) = 0 if and only if i − 1 = n − i, which occurs precisely when n is odd. Moreover, (i−1)⊕(n−i) = 1 if and only if i−1 is even and n−i = (i−1)+1, or n−i is even and i − 1 = (n − i) + 1, and either case occurs precisely when n is even. Therefore, if n is odd, then {G((L_{n×2})_{v}) : v ∈ V (L_{n×2})} contains 0 but not 1, implying that G(L_{n×2}) = mex{G((L_{n×2})_{v}) : v ∈ V (L_{n×2})} = 1; if n is even, then {G((L_{n×2})_{v}) : v ∈ V (L_{n×2})} does not contain 0, implying that G(L_{n×2}) = mex{G((L_{n×2})_{v}) : v ∈ V (L_{n×2})} = 0.

Similar to the proof technique above, we list out the Nimber of the Node-Kayles game on the residue subgraph (L_{n×2}^{−})_{v} for each vertex v in the following table.

Vertex v  G((L_{n×2}^{−})_{v})
v_{i,1}, where 1 ≤ i ≤ n  G(L_{(i−2)×2}^{−}) ⊕ G(^{−}L_{(n−i−1)×2}^{−}) = (i − 1) ⊕ 1
v_{i,2}, where 1 ≤ i ≤ n  G(L_{(i−2)×2}^{−}) ⊕ G(_{−}L_{(n−i−1)×2}^{−}) = (i − 1) ⊕ 0 = i − 1
v_{n+1,2}  G(L_{(n−1)×2}^{−}) = n

Note that for 1 ≤ i ≤ n, the quantity (i − 1) ⊕ 1 = i − 2 if i is even and (i − 1) ⊕ 1 = i if i is odd. Therefore,

G(L_{n×2}^{−}) = mex ({i − 2 : 1 ≤ i ≤ n and i is even} ∪ {i : 1 ≤ i ≤ n and i is odd}
∪ {i − 1 : 1 ≤ i ≤ n} ∪ {n})
= mex{0, 1, 2, …, n} = n + 1.

To find G(^{−}L_{n×2}^{−}), we create the following table.

Vertex v  G((^{−}L_{n×2}^{−})_{v})
v_{i,1}, where 1 ≤ i ≤ n  G(^{−}L_{(i−2)×2}^{−}) ⊕ G(^{−}L_{(n−i−1)×2}^{−}) = 1 ⊕ 1 = 0
v_{i,2}, where 1 ≤ i ≤ n  G(_{−}L_{(i−2)×2}^{−}) ⊕ G(_{−}L_{(n−i−1)×2}^{−}) = 0 ⊕ 0 = 0
v_{0,2} or v_{n+1,2}  G(_{−}L_{(n−1)×2}^{−}) = 0

Therefore, G(^{−}L_{n×2}^{−}) = mex{0} = 1.

Finally, to find G(_{−}L_{n×2}^{−}), we create the following table.

Vertex v  G((_{−}L_{n×2}^{−})_{v})
v_{i,1}, where 1 ≤ i ≤ n  G(_{−}L_{(i−2)×2}^{−}) ⊕ G(^{−}L_{(n−i−1)×2}^{−}) = 0 ⊕ 1 = 1
v_{i,2}, where 1 ≤ i ≤ n  G(^{−}L_{(i−2)×2}^{−}) ⊕ G(_{−}L_{(n−i−1)×2}^{−}) = 1 ⊕ 0 = 1
v_{0,1} or v_{n+1,2}  G(^{−}L_{(n−1)×2}^{−}) = 1

Therefore, G(_{−}L_{n×2}^{−}) = mex{1} = 0, and this completes the induction.

An immediate application of the proof of Theorem 2 is the following corollary on prism graphs. For any integer n ≥ 3, a prism of order n, denoted by Π_{n}, is the Cartesian product C_{n}□P_{2}. It is essentially a circular ladder with the vertex set {v_{i,j} : 1 ≤ i ≤ n, 1 ≤ j ≤ 2} and the edge set {v_{i,j}v_{i′,j′} : |i − i′| + |j − j′| = 1} ∪ {v_{1,1}v_{n,1}, v_{1,2}v_{n,2}}.

Corollary 3. The Nimber sequence (G(Π_{n}) : n ≥ 3) is constantly 0.

Proof. After any move of the first player, the residue graph is always isomorphic to^{−}L_{(n−3)×2}^{−}. From the proof of Theorem 2, G(^{−}L_{(n−3)×2}^{−}) = 1 for all integers n ≥ 3. Therefore, G(Π_{n}) = mex{G((Π_{n})_{v}) : v ∈ V (Π_{n})} = mex{1} = 0.

Similar to the proof of Theorem 1, the technique in the proof of Theorem 2 is to recursively compute the Nimbers of residue graphs. This technique is efficient since most residue graphs of 3-paths and ladder graphs are disconnected, and each connected component is always one of the few variations of the original graphs. Unfortunately, many residue graphs of lattices L_{n×m} are connected when n and m are greater than 2. As a result, this method is far too tedious to be applied to larger lattice graphs. For example, to determine the Nimber of the Node-Kayles game on L_{3×3}, we need to first find that

G(  ) = mex{G(  ), G(  ), G(  ), G(  ), G(  ), G(  )}
= mex{G(^{−}L_{1×2}^{−}), G(P_{2}), 1 ⊕ 1 ⊕ 1, 1 ⊕ 1 ⊕ 1, G(P_{2}), G(^{−}L_{1×2}^{−})}
= mex{1, 1, 1, 1, 1, 1} = 0,

before we find

G(L_{3×3}) = mex{G(  ), G( ), G(  )}
= mex{0, G(P_{5}), 1 ⊕ 1 ⊕ 1 ⊕ 1) = mex{0, 3, 0} = 1.

The complexity of this process drastically increases when we try to determine G(L_{5×3}) with this method. Hence, in order to study the Nimber sequence of the Node-Kayles game on lattice graphs in general, we need to adopt another approach.

Recall from the introduction that the Nimber of an impartial game is 0 if and only if it is second-player winning. The following theorem specifies graphs with a special property that will guarantee a winning strategy for the second-player. This theorem also appears in the work of Duchêne et. al. [3], but the proof is included here for completion.

Theorem 4. Let G be a simple graph. If there exists a graph involution φ on G such that for all v ∈ V (G), φ(v) is neither v nor a neighbor of v in G, then G(G) = 0.

Proof. In the first player’s initial move, if the closed neighborhood N_{G}[v] of a vertex v is removed from G, then the strategy of the second player is to remove N_{G}[φ(v)] from G. Note that this move is legal since φ(v) cannot be removed by the first player, as φ(v) ∉ N_{G}[v].

Denote the residue graph after the second player’s initial move as

H := G − (N_{G}[v] ∪ N_{G}[φ(v)]).

Note that for every vertex u ∈ H, since u ∉ N_{G}[v], φ(u) ∉ N_{G}[φ(v)]. Also, since u ∉ N_{G}[φ(v)], φ(u) ∉ N_{G}[φ^{2}(v)] = N_{G}[v]. Hence, φ(u) ∈ H, and φ|_{H} is a well-defined graph homomorphism. As a result, φ|_{H} is a graph involution on H such that for all u ∈ V (H), φ(u) is neither u nor a neighbor of u in G. Hence, we can inductively apply the strategy described above.

We are going to apply Theorem 4 on some lattice graphs.

Theorem 5. The Nimber G(L_{n×m}) is 0 if both n and m are even, and is positive if both n and m are odd.

Proof. If both n and m are even, then let φ be a graph automorphism on L_{n×m} such that φ(v_{i,j}) = v_{n+1−i,m+1−j}. Essentially, φ rotates the lattice graph by 180^{∘}. It is easy to check that φ is an involution that satisfies the condition in Theorem 4, so G(L_{n×m}) = 0.

If both n and m are odd, then let φ be a graph automorphism on (L_{n×m})_{v_{\frac{n+1}{2} , \frac{m+1}{2}}} such that φ(v_{i,j}) = v_{n+1−i,m+1−j}. Once again, φ is an involution that satisfies the condition in Theorem 4, so G((L_{n×m})_{v_{\frac{n+1}{2} , \frac{m+1}{2}}} ) = 0. As a result, \{G((L_{n×m})_{v}) : v ∈ V (L_{n×m})\} contains 0, and hence, G(L_{n×m}) = mex{G((L_{n×m})_{v}) : v ∈ V (L_{n×m})} > 0.

The winning strategy given by the graph involution described in Theorem 4 is by no means the only one. In particular, we find another winning strategy for the second player on lattice graphs L_{n×4} in the following theorem.

Theorem 6. For all positive integers n, G(L_{n×4}) = 0.

Proof. Define property (P) of a graph as follows: for any 1 ≤ i ≤ n and 1 ≤ j ≤ 4, the vertex v_{i,j} is in the graph if and only if the vertex v_{i,j+2} is in the graph, where j + 2 is performed under modulo 4.

At the beginning of the game, the lattice graph L_{n×4} clearly satisfies property (P). After any move of the first player, if the closed neighborhood N_{(L_{n×4})}[v_{i,j}] of the vertex v_{i,j} is removed from L_{n×4}, then the strategy of the second player is to remove N_{(L_{n×4})}[v_{i,j+2}], where j +2 is performed under modulo 4. After the move of the second player, note that the residue graph still satisfies property (P). As a result, the second player can win the Node-Kayles game by inductively applying the strategy described above.

Table 1 summarizes our results on the Nimbers G(L_{n×m}) for 1 ≤ n, m ≤ 10. Note that the values in shaded cells are computed using Python. The computer code, together with the first few terms in the sequence (G(L_{n×3}) : n ∈ ℕ), are listed on the OEIS as \underline{A316632} [7].

m n 1  2  3  4  5  6  7  8  9 10
1  1  1  2  0  3  1  1  0  3  3
2  1  0  1  0  1  0  1  0  1  0
3  2  1  1  0  3  3  2  2  2  3
4  0  0  0  0  0  0  0  0  0  0
5  3  1  3  0  3  3  2  > 0
6  1  0  3  0  3  0  0  0
7  1  1  2  0  2  > 0  > 0
8  0  0  2  0  0  0  0
9  3  1  2  0 > 0  > 0  > 0
10  3  0  3  0  0  0  0

Table 1: Table of Nimbers G(L_{n×m}), where shaded cells are computed using Python

4 Chained and linked cliques

In this section, we consider infinite families of graphs constructed using cliques as building blocks. An n-chained clique, denoted by CK_{n}, is a graph with n cliques {K_{i_{j}} : 1 ≤ j ≤ n} linked together such that

(a) V (K_{i_{j}}) ∩ V (K_{i_{j′}}) ≠ ∅ if and only if |j − j′| = 1, and

(b) V (K_{i_{j}}) \ (⋃_{j′≠j} V (K_{i_{j′}})) ≠ ∅ if and only if j = 1 or n.

If condition (b) is replaced by

(c) V (K_{i_{j}}) \ (⋃_{j′≠j} V (K_{i_{j′}})) ≠ ∅ for 1 ≤ j ≤ n,

then the resultant graph is called an n-linked clique, denoted by LK_{n}. Note that in an n-chained clique, conditions (a) and (b) imply that i_{j} ≥ 2 for all 1 ≤ j ≤ n, while in an n-linked clique, conditions (a) and (c) imply that i_{j} ≥ 3 for all 2 ≤ j ≤ n − 1.

\begin{matrix}K_{4} \\ K_{5} \\ K_{8} \\ K_{6} \\ K_{5} \\ K_{4} \\ K_{2} \\ K_{3} \end{matrix}

Figure 10: An 8-chained clique that chains up K_{4}, K_{5}, K_{8}, K_{6}, K_{5}, K_{4}, K_{2}, K_{3}

\begin{matrix}K_{4} \\ K_{5} \\ K_{7} \\ K_{7} \\ K_{3} \\ K_{4} \\ K_{6} \\ K_{3} \end{matrix}

Figure 11: An 8-linked clique that links up K_{4}, K_{5}, K_{7}, K_{7}, K_{3}, K_{4}, K_{6}, K_{3}

When we try to analyze the Node-Kayles game on the n-chained cliques, we discover that the Nimber sequence is quite familiar to us. In fact, for any vertex v in V (K_{i_{j}}) ∩ V (K_{i_{j+1}}), 1 ≤ j ≤ n − 1, the set of neighbors N(v) is exactly V (K_{i_{j}}) ∪ V (K_{i_{j+1}}). Hence, collapsing each of V (K_{i_{1}}) \ V (K_{i_{2}}), V (K_{i_{j}}) ∩ V (K_{i_{j+1}}) with 1 ≤ j ≤ n − 1, and V (K_{i_{n}}) \ V (K_{i_{n−1}}) to a single vertex yields a graph whose Node-Kayles game is equivalent to the original n-chained clique. This resultant collapsed graph is precisely the path graph P_{n+1}, which implies that G(CK_{n}) = G(P_{n+1}) for all n ∈ ℕ.

Figure 12: Transforming a CK_{8} to P_{9}

As for LK_{n}, note that for any vertex v in V (K_{i_{j}}) \ (⋃_{j′≠j} V (K_{i_{j′}})), where 1 ≤ j ≤ n, the set of neighbors N(v) is V (K_{i_{j}}), and for any vertex u in V (K_{i_{j}}) ∩ V (K_{i_{j+1}}), where 1 ≤ j ≤ n − 1, the set of neighbors N(u) is V (K_{i_{j}}) ∪ V (K_{i_{j+1}}). Hence, collapsing each of

V (K_{i_{j}}) \ (⋃_{j′≠j} V (K_{i_{j′}})) with 1 ≤ j ≤ n and V (K_{i_{j}}) ∩ V (K_{i_{j+1}}) with 1 ≤ j ≤ n − 1 to a single vertex yields a graph whose Node-Kayles game is equivalent to the original n-linked clique. This resultant collapsed graph is an n-linked clique that links up n − 2 copies of K_{3} with a copy of K_{2} on each end. To be precise, the vertex set of this resultant graph is {v_{1}, v_{2}, …, v_{n}, u_{1}, u_{2}, …, u_{n−1}}, and the edge set is {v_{j}u_{j}, u_{j}v_{j+1} : 1 ≤ j ≤ n − 1} ∪ {u_{j}u_{j+1} : 1 ≤ j ≤ n − 2}. We call this graph a triangular path, denoted by T_{n}, despite each of the two ends of the triangular path has a pendant vertex.

\begin{matrix}v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ v_{6} \\ v_{7} \\ v_{8} \\ u_{1} \\ u_{2} \\ u_{3} \\ u_{4} \\ u_{5} \\ u_{6} \\ u_{7} \end{matrix}

Figure 13: Transforming an LK_{8} to T_{8}

To find G(T_{n}), we first extend the definition of T_{n} to include the case n = 0, where T_{0} is defined as the empty graph. Next, we exhaust all possible first moves in the Node-Kayles game on T_{n} and obtain the following recursions.

\begin{cases}G((T_{n})_{v_{j}}) = G(T_{j−1}) ⊕ G(T_{n−j}), & for 1 ≤ j ≤ n; \\ G((T_{n})_{u_{j}}) = G(T_{j−1}) ⊕ G(T_{n−j−1}), & for 1 ≤ j ≤ n − 1. \end{cases}  (4)

Recursions (4) are identical to the recursion given by the game of Kayles, introduced in Section 1, and both games are equivalent to an octal game ·77. The equivalence can be seen by identifying T_{n} as a heap of n beans, where each v_{j} is a bean. Removing exactly one bean can be performed by removing N_{(T_{n})}[v_{j}] from T_{n} in the Node-Kayles game, and such action may completely remove the heap if n = j = 1, may reduce the size of the heap if n ≥ 2 and j = 1 or n, and may split the heap into two smaller heaps if n ≥ 3 and 2 ≤ j ≤ n − 1; so d_{1} = 7. Removing exactly two beans can be performed by removing N_{(T_{n})}[u_{j}] from T_{n} in the Node-Kayles game, and such action may completely remove the heap if n = 2 and j = 2, may reduce the size of the heap if n ≥ 3 and j = 1 or n − 1, and may split the heap into two smaller heaps if n ≥ 4 and 2 ≤ j ≤ n − 2; so d_{2} = 7. Finally, it is easy to see that it is impossible to remove three or more beans in one move.

In conclusion, the Nimber sequence (G(LK_{n}) : n ∈ ℕ) = (G(T_{n}) : n ∈ ℕ) is given by the OEIS sequence \underline{A002186} [7].

5 Linked cycles and linked diamonds

In the previous section, we constructed the triangular path T_{n} (see Figure 13). Clearly, for the purpose of studying the Node-Kayles game, replacing the pendant edge on each end of T_{n} by a triangle does not change the game. Triangles, in the previous section, were treated as complete graphs, but we can also think of them as cycles. In this section, we consider infinite families of graphs constructed using cycles of the same length as building blocks. An (ℓ, n)-linked k-cycle, denoted by (C_{k})_{ℓ,n}, is a graph with n copies of C_{k} linked together at vertices u_{i}, 1 ≤ i ≤ n − 1, such that the distance between u_{i} and u_{i+1} is ℓ. To be precise, to form an (ℓ, n)-linked k-cycle (C_{k})_{ℓ,n}, we begin with a collection of n copies of k-cycles {v_{i,0}v_{i,1}v_{i,2} ⋯ v_{i,k−1}v_{i,0} : 1 ≤ i ≤ n}, and we identify vertices such that v_{i,ℓ} = v_{i+1,0} = u_{i} for all 1 ≤ i ≤ n − 1. The vertex v_{n,ℓ} will also be called v_{n+1,0}.

\begin{matrix}v_{1,0} \\ v_{1,1} \\ v_{1,2} \\ v_{1,3} \\ v_{2,0} \\ v_{2,1} \\ v_{2,2} \\ v_{2,3} \\ v_{3,0} \\ v_{3,1} \\ v_{3,2} \\ v_{3,3} \\ v_{4,0} \\ v_{4,1} \\ v_{4,2} \\ v_{4,3} \\ v_{5,0} \\ v_{5,1} \\ v_{5,2} \\ v_{5,3} \end{matrix}

\begin{matrix}v_{1,0} \\ v_{1,1} = v_{2,0} \\ v_{1,2} \\ v_{1,3} \\ v_{2,1} = v_{3,0} \\ v_{2,2} \\ v_{2,3} \\ v_{3,1} = v_{4,0} \\ v_{3,2} \\ v_{3,3} \\ v_{4,1} = v_{5,0} \\ v_{4,2} \\ v_{4,3} \\ v_{5,1} = v_{6,0} \\ v_{5,2} \\ v_{5,3} \end{matrix}  \begin{matrix}v_{1,3} \\ v_{1,1} \\ v_{2,3} \\ v_{2,1} \\ v_{3,3} \\ v_{3,1} \\ v_{4,3} \\ v_{4,1} \\ v_{5,3} \\ v_{5,1} \\ v_{1,0} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \end{matrix}

Figure 14: Linking 5 copies of C_{4} (top) as (C_{4})_{1,5} (bottom left) or (C_{4})_{2,5} (bottom right)

In this section, we completely determine the Nimber sequences (G((C_{4})_{2,n}) : n ∈ ℕ) and (G((C_{5})_{2,n}) : n ∈ ℕ). We will also study the recursion of the Nimber sequence (G((C_{4})_{1,n}) : n ∈ ℕ); however, this recursion does not give us a closed form, which is mildly surprising.

To determine the Nimber sequence (G((C_{4})_{2,n}) : n ∈ ℕ), we need to further define two related families of graphs. The first variation, denoted by (C_{4})_{2,n}^{<}, is a (2, n)-linked 4-cycle with additional vertices v_{n+1,1} and v_{n+1,3} and additional edges v_{n,2}v_{n+1,1} and v_{n,2}v_{n+1,3}; the second variation, denoted by ^{>}(C_{4})_{2,n}^{<}, is the first variation (C_{4})_{2,n}^{<} with additional vertices v_{0,1} and v_{0,3} and additional edges v_{0,1}v_{1,0} and v_{0,3}v_{1,0}. Figures 15 and 16 are examples of the first and second variations of a (2, n)-linked 4-cycle, respectively.

\begin{matrix}v_{1,3} \\ v_{1,1} \\ v_{2,3} \\ v_{2,1} \\ v_{3,3} \\ v_{3,1} \\ v_{4,3} \\ v_{4,1} \\ v_{5,3} \\ v_{5,1} \\ v_{6,3} \\ v_{6,1} \\ v_{7,3} \\ v_{7,1} \\ v_{1,0} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \end{matrix}

Figure 15: The first variation of the (2, 6)-linked 4-cycle (C_{4})_{2,6}^{<}

\begin{matrix}v_{0,3} \\ v_{0,1} \\ v_{1,3} \\ v_{1,1} \\ v_{2,3} \\ v_{2,1} \\ v_{3,3} \\ v_{3,1} \\ v_{4,3} \\ v_{4,1} \\ v_{5,3} \\ v_{5,1} \\ v_{6,3} \\ v_{6,1} \\ v_{7,3} \\ v_{7,1} \\ v_{1,0} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \end{matrix}

Figure 16: The second variation of the (2, 6)-linked 4-cycle ^{>}(C_{4})_{2,6}^{<}

Theorem 7. The Nimber sequences (G((C_{4})_{2,n}) : n ∈ ℕ), (G((C_{4})_{2,n}^{<}) : n ∈ ℕ), and (G(^{>}(C_{4})_{2,n}^{<}) : n ∈ ℕ) are given by the following:

G((C_{4})_{2,n}) = \begin{cases}0, & if n is odd; \\ 1, & otherwise \end{cases}

and

G((C_{4})_{2,n}^{<}) = G(^{>}(C_{4})_{2,n}^{<}) = \begin{cases}0, & if n is odd; \\ 2, & otherwise. \end{cases}

Proof. First, note that (C_{4})_{2,1} is isomorphic to the lattice graph L_{2×2}, so G((C_{4})_{2,1}) = G(L_{2×2}) = 0 by Theorem 2. We can also easily see that

G((C_{4})_{2,1}^{<}) = G(  ) = mex{G(  ), G(  ), G(  ), G(  )}
= mex{G(P_{3}), 1 ⊕ 1 ⊕ 1, 1, G(P_{3}) ⊕ 1}
= mex{2, 1, 1, 3} = 0,

and

G(^{>}(C_{4})_{2,1}^{<}) = G(  ) = mex{G(  ), G(  ), G(  )}
= mex{1 ⊕ mex{G( ), G(∅)}, G(P_{3}), 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1}
= mex{1 ⊕ 2, 2, 1} = 0.

Hence, the base cases for our strong induction are true.

Before we proceed with our induction proof, it is convenient to extend the definitions of (C_{4})_{2,n}, (C_{4})_{2,n}^{<}, and^{>}(C_{4})_{2,n}^{<} to the cases when −1 ≤ n ≤ 0 and determine the corresponding Nimbers as follows.

n (C_{4})_{2,n} G((C_{4})_{2,n}) (C_{4})_{2,n}^{<} G((C_{4})_{2,n}^{<}) ^{>}(C_{4})_{2,n}^{<} G(^{>}(C_{4})_{2,n}^{<})
−1  ∅  0  ∅  0  0

0  1  2  2

Now, we are ready to finish our proof by strong induction. Assume that for some integer n ≥ 2,

G((C_{4})_{2,i}) = \begin{cases}0, & if n is odd; \\ 1, & otherwise \end{cases}

and

G((C_{4})_{2,i}^{<}) = G(^{>}(C_{4})_{2,i}^{<}) = \begin{cases}0, & if n is odd; \\ 2, & otherwise \end{cases}

for all integers −1 ≤ i < n. To find G((C_{4})_{2,n}), we exhaust all possible first moves in the Node-Kayles game on (C_{4})_{2,n}. For each 1 ≤ i ≤ n + 1,

G(((C_{4})_{2,n})_{v_{i,0}}) = G((C_{4})_{2,i−2}) ⊕ G((C_{4})_{2,n−i})
= \begin{cases}0 ⊕ 1 or 1 ⊕ 0, & if n is odd; \\ 0 ⊕ 0 or 1 ⊕ 1, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 0, & otherwise, \end{cases}

and for 1 ≤ i ≤ n,

G(((C_{4})_{2,n})_{v_{i,1}}) = G(((C_{4})_{2,n})_{v_{i,3}}) = G((C_{4})_{2,i−2}^{<}) ⊕ 1 ⊕ G((C_{4})_{2,n−i−1}^{<})

= \begin{cases}0 ⊕ 1 ⊕ 0 or 2 ⊕ 1 ⊕ 2, & if n is odd; \\ 0 ⊕ 1 ⊕ 2 or 2 ⊕ 1 ⊕ 0, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise. \end{cases}

Therefore,

G((C_{4})_{2,n}) = \begin{cases}mex\{1, 1\}, & if n is odd; \\ mex\{0, 3\}, & otherwise \end{cases} = \begin{cases}0, & if n is odd; \\ 1, & otherwise. \end{cases}

To find G((C_{4})_{2,n}^{<}), we exhaust all possible first moves in the Node-Kayles game on (C_{4})_{2,n}^{<}.

For each 1 ≤ i ≤ n + 1,

G(((C_{4})_{2,n}^{<})_{v_{i,0}}) = G((C_{4})_{2,i−2}) ⊕ G((C_{4})_{2,n−i}^{<})
= \begin{cases}0 ⊕ 2 or 1 ⊕ 0, & if n is odd; \\ 0 ⊕ 0 or 1 ⊕ 2, & otherwise \end{cases}

= \begin{cases}2 or 1, & if n is odd; \\ 0 or 3, & otherwise, \end{cases}

for 1 ≤ i ≤ n,

G(((C_{4})_{2,n}^{<})_{v_{i,1}}) = G(((C_{4})_{2,n}^{<})_{v_{i,3}}) = G((C_{4})_{2,i−2}^{<}) ⊕ 1 ⊕ G(^{>}(C_{4})_{2,n−i−1}^{<})

= \begin{cases}0 ⊕ 1 ⊕ 0 or 2 ⊕ 1 ⊕ 2, & if n is odd; \\ 0 ⊕ 1 ⊕ 2 or 2 ⊕ 1 ⊕ 0, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise, \end{cases}

and for i = n + 1,

G(((C_{4})_{2,n}^{<})_{v_{n+1,1}}) = G(((C_{4})_{2,n}^{<})_{v_{n+1,3}}) = G((C_{4})_{2,n−1}^{<}) ⊕ 1
= \begin{cases}2 ⊕ 1, & if n is odd; \\ 0 ⊕ 1, & otherwise \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise. \end{cases}

Therefore,

G((C_{4})_{2,n}^{<}) = \begin{cases}mex\{2, 1, 1, 3\}, & if n is odd; \\ mex\{0, 3, 3, 1\}, & otherwise \end{cases} = \begin{cases}0, & if n is odd; \\ 2, & otherwise. \end{cases}

To find G(^{>}(C_{4})_{2,n}^{<}), we exhaust all possible first moves in the Node-Kayles game on >(C_{4})_{2,n}^{<}. For each 1 ≤ i ≤ n + 1,

G((^{>}(C_{4})_{2,n}^{<})_{v_{i,0}}) = G((C_{4})_{2,i−2}^{<}) ⊕ G((C_{4})_{2,n−i}^{<})
= \begin{cases}0 ⊕ 2 or 2 ⊕ 0, & if n is odd; \\ 0 ⊕ 0 or 2 ⊕ 2, & otherwise \end{cases}

= \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

for 1 ≤ i ≤ n,

G((^{>}(C_{4})_{2,n}^{<})_{v_{i,1}}) = G((^{>}(C_{4})_{2,n}^{<})_{v_{i,3}}) = G(^{>}(C_{4})_{2,i−2}^{<}) ⊕ 1 ⊕ G(^{>}(C_{4})_{2,n−i−1}^{<})

= \begin{cases}0 ⊕ 1 ⊕ 0 or 2 ⊕ 1 ⊕ 2, & if n is odd; \\ 0 ⊕ 1 ⊕ 2 or 2 ⊕ 1 ⊕ 0, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise, \end{cases}

and for i = 0 or n + 1,

G((^{>}(C_{4})_{2,n}^{<})_{v_{i,1}}) = G((^{>}(C_{4})_{2,n}^{<})_{v_{i,3}}) = G(^{>}(C_{4})_{2,n−1}^{<}) ⊕ 1
= \begin{cases}2 ⊕ 1, & if n is odd; \\ 0 ⊕ 1, & otherwise \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise. \end{cases}

Therefore,

G(^{>}(C_{4})_{2,n}^{<}) = \begin{cases}mex\{2, 1, 3\}, & if n is odd; \\ mex\{0, 3, 1\}, & otherwise \end{cases} = \begin{cases}0, & if n is odd; \\ 2, & otherwise. \end{cases}

To determine the Nimber sequence (G((C_{5})_{2,n}) : n ∈ ℕ), we need to further define five related families of graphs. The first variation, denoted by (C_{5})_{2,n}^{−}, is a (2, n)-linked 5-cycle with an additional vertex v_{n+1,1} and an additional edge v_{n,2}v_{n+1,1}; the second variation, denoted by (C_{5})_{2,n}^{⊏}, is the first variation (C_{5})_{2,n}^{−} with additional vertices v_{n+1,3} and v_{n+1,4} and an additional path v_{n,2}v_{n+1,4}v_{n+1,3}; the third variation, denoted by ^{−}(C_{5})_{2,n}^{−}, is the first variation (C_{5})_{2,n}^{−} with an additional vertex v_{0,1} and an additional edge v_{0,1}v_{1,0}; the fourth variation, denoted by ^{−}(C_{5})_{2,n}^{⊏}, is the second variation (C_{5})_{2,n}^{⊏} with an additional vertex v_{0,1} and an additional edge v_{0,1}v_{1,0}; the fifth variation, denoted by^{⊐}(C_{5})_{2,n}^{⊏}, is the fourth variation −(C_{5})_{2,n}^{⊏} with additional vertices v_{0,3} and v_{0,4} and an additional path v_{0,4}v_{0,3}v_{1,0}. Figures 17 to 22 are examples of a (2, n)-linked 5-cycle and its first to fifth variations, respectively.

\begin{matrix}v_{1,1} \\ v_{1,3} \\ v_{1,4} \\ v_{2,1} \\ v_{2,3} \\ v_{2,4} \\ v_{3,1} \\ v_{3,3} \\ v_{3,4} \\ v_{4,1} \\ v_{4,3} \\ v_{4,4} \\ v_{5,1} \\ v_{5,3} \\ v_{5,4} \\ v_{6,1} \\ v_{6,3} \\ v_{6,4} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \\ v_{1,0} \end{matrix}

Figure 17: The (2, 6)-linked 5-cycle (C_{5})_{2,6}

\begin{matrix}v_{1,1} \\ v_{1,3} \\ v_{1,4} \\ v_{2,1} \\ v_{2,3} \\ v_{2,4} \\ v_{3,1} \\ v_{3,3} \\ v_{3,4} \\ v_{4,1} \\ v_{4,3} \\ v_{4,4} \\ v_{5,1} \\ v_{5,3} \\ v_{5,4} \\ v_{6,1} \\ v_{6,3} \\ v_{6,4} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \\ v_{1,0} \\ v_{7,1} \end{matrix}

Figure 18: The first variation of the (2, 6)-linked 5-cycle (C_{5})_{2,6}^{−}

\begin{matrix}v_{1,1} \\ v_{1,3} \\ v_{1,4} \\ v_{2,1} \\ v_{2,3} \\ v_{2,4} \\ v_{3,1} \\ v_{3,3} \\ v_{3,4} \\ v_{4,1} \\ v_{4,3} \\ v_{4,4} \\ v_{5,1} \\ v_{5,3} \\ v_{5,4} \\ v_{6,1} \\ v_{6,3} \\ v_{6,4} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \\ v_{1,0} \\ v_{7,1} \\ v_{7,3} \\ v_{7,4} \end{matrix}

Figure 19: The second variation of the (2, 6)-linked 5-cycle (C_{5})_{2,6}^{⊏}

\begin{matrix}v_{1,1} \\ v_{1,3} \\ v_{1,4} \\ v_{2,1} \\ v_{2,3} \\ v_{2,4} \\ v_{3,1} \\ v_{3,3} \\ v_{3,4} \\ v_{4,1} \\ v_{4,3} \\ v_{4,4} \\ v_{5,1} \\ v_{5,3} \\ v_{5,4} \\ v_{6,1} \\ v_{6,3} \\ v_{6,4} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \\ v_{1,0} \\ v_{7,1} \\ v_{0,1} \end{matrix}

Figure 20: The third variation of the (2, 6)-linked 5-cycle ^{−}(C_{5})_{2,6}^{−}

\begin{matrix}v_{1,1} \\ v_{1,3} \\ v_{1,4} \\ v_{2,1} \\ v_{2,3} \\ v_{2,4} \\ v_{3,1} \\ v_{3,3} \\ v_{3,4} \\ v_{4,1} \\ v_{4,3} \\ v_{4,4} \\ v_{5,1} \\ v_{5,3} \\ v_{5,4} \\ v_{6,1} \\ v_{6,3} \\ v_{6,4} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \\ v_{1,0} \\ v_{7,1} \\ v_{7,3} \\ v_{7,4} \\ v_{0,1} \end{matrix}

Figure 21: The fourth variation of the (2, 6)-linked 5-cycle ^{−}(C_{5})_{2,6}^{⊏}

\begin{matrix}v_{1,1} \\ v_{1,3} \\ v_{1,4} \\ v_{2,1} \\ v_{2,3} \\ v_{2,4} \\ v_{3,1} \\ v_{3,3} \\ v_{3,4} \\ v_{4,1} \\ v_{4,3} \\ v_{4,4} \\ v_{5,1} \\ v_{5,3} \\ v_{5,4} \\ v_{6,1} \\ v_{6,3} \\ v_{6,4} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \\ v_{1,0} \\ v_{7,1} \\ v_{7,3} \\ v_{7,4} \\ v_{0,1} \\ v_{0,4} \\ v_{0,3} \end{matrix}

Figure 22: The fifth variation of the (2, 6)-linked 5-cycle ^{⊐}(C_{5})_{2,6}^{⊏}

Theorem 8. The Nimber sequences (G((C_{5})_{2,n}) : n ∈ ℕ), (G((C_{5})_{2,n}^{−}) : n ∈ ℕ), (G((C_{5})_{2,n}^{⊏}) : n ∈ ℕ), (G(^{−}(C_{5})_{2,n}^{−}) : n ∈ ℕ), (G(^{−}(C_{5})_{2,n}^{⊏}) : n ∈ ℕ), and (G(^{⊐}(C_{5})_{2,n}^{⊏}) : n ∈ ℕ) are given by the following:

G((C_{5})_{2,n}) = G(^{−}(C_{5})_{2,n}^{−}) = G(^{⊐}(C_{5})_{2,n}^{⊏}) = \begin{cases}0, & if n is odd; \\ 2, & otherwise, \end{cases}

G((C_{5})_{2,n}^{−}) = \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases} G((C_{5})_{2,n}^{⊏}) = \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

and G(^{−}(C_{5})_{2,n}^{⊏}) = \begin{cases}1, & if n is odd; \\ 3, & otherwise. \end{cases}

Proof. First, we are going to prove the base cases for our strong induction.

G((C_{5})_{2,1}) = G( ) = mex{G( )} = mex{G(P_{2})} = mex{1} = 0.

G((C_{5})_{2,1}^{−}) = G(  ) = mex{G(  ), G(  ), G(  ), G(  )}
= mex{G(P_{3}), G(P_{2}) ⊕ 1, G(P_{2}), G(P_{4})}
= mex{2, 1 ⊕ 1, 1, 0} = 3.

G((C_{5})_{2,1}^{⊏}) = G( )
= mex{G(  ), G(  ), G(  ), G(  ), G(  ), G(  )}
= mex{mex{G(  ), G(  ), G(  ), G(  )}, G(P_{2}) ⊕ G(P_{2}) ⊕ 1,
G(P_{2}) ⊕ 1, G(P_{4}) ⊕ G(P_{2}), G(P_{4}) ⊕ 1, G((C_{5})_{2,1}^{−})}
= mex{mex{0, 1, 0, 2}, 1 ⊕ 1 ⊕ 1, 1 ⊕ 1, 0 ⊕ 1, 0 ⊕ 1, 3} = 2.

G(^{−}(C_{5})_{2,1}^{−}) = G(  ) = mex{G(  ), G(  ), G(  ), G(  )}
= mex{3, G(P_{3}), 1 ⊕ G(P_{2}) ⊕ 1, 1 ⊕ G(P_{3})}
= mex{3, 2, 1 ⊕ 1 ⊕ 1, 1 ⊕ 2} = 0.

G(^{−}(C_{5})_{2,1}^{⊏}) = G( )

= mex{G(  ), G(  ), G(  ), G(  ), G(  ),
G(  ), G(  ), G(  ), G(  )}
= mex{mex{G(  ), G(  ), G(  ), G(  )}, 3,

1 ⊕ G(P_{2}) ⊕ G(P_{2}) ⊕ 1, G(P_{3}) ⊕ 1, G(P_{3}) ⊕ G(P_{2}) ⊕ 1, 1 ⊕ 3, 3 ⊕ G(P_{2}),

3 ⊕ 1, G(^{−}(C_{5})_{2,1}^{−})}

= mex{mex{1, 0, 1, 3}, 3, 1 ⊕ 1 ⊕ 1 ⊕ 1, 2 ⊕ 1, 2 ⊕ 1 ⊕ 1, 2, 3 ⊕ 1, 2, 0} = 1.

G(^{⊐}(C_{5})_{2,1}^{⊏}) = G( )

= mex{G(  ), G(  ), G(  ), G(  ), G(  ),
G( )}

= mex{G(P_{2}) ⊕ 2, 1 ⊕ 3, 1 ⊕ 2, G(^{−}(C_{5})_{2,1}^{⊏}), 1 ⊕ G(P_{2}) ⊕ G(P_{2}) ⊕ G(P_{2}) ⊕ 1,

1 ⊕ G(P_{2}) ⊕ 3} = mex{3, 2, 3, 1, 1, 3} = 0.

Before we proceed with our induction proof, it is convenient to extend the definitions of (C_{5})_{2,n}^{−}, (C_{5})_{2,n}^{⊏}, and ^{−}(C_{5})_{2,n}^{−} to the case when n = 0, as well as the definitions of ^{−}(C_{5})_{2,n}^{⊏} and ^{⊐}(C_{5})_{2,n}^{⊏} to the cases when −1 ≤ n ≤ 0 and determine the corresponding Nimbers as follows.

n (C_{5})_{2,n}^{−} G((C_{5})_{2,n}^{−}) (C_{5})_{2,n}^{⊏} G((C_{5})_{2,n}^{⊏}) ^{−}(C_{5})_{2,n}^{−} G(^{−}(C_{5})_{2,n}^{−})
0  1  0  2

n ^{−}(C_{5})_{2,n}^{⊏} G(^{−}(C_{5})_{2,n}^{⊏}) ^{⊐}(C_{5})_{2,n}^{⊏}  G(^{⊐}(C_{5})_{2,n}^{⊏})
−1  1  0

0  3  2

Now, we are ready to finish our proof by strong induction. Assume that for some integer n ≥ 2,

G((C_{5})_{2,i}) = \begin{cases}0, & if i is odd; \\ 2, & otherwise \end{cases}

for all integers 1 ≤ i < n,

G((C_{5})_{2,i}^{−}) = \begin{cases}3, & if i is odd; \\ 1, & otherwise, \end{cases} G((C_{5})_{2,i}^{⊏}) = \begin{cases}2, & if i is odd; \\ 0, & otherwise, \end{cases}

and G(^{−}(C_{5})_{2,i}^{−}) = \begin{cases}0, & if i is odd; \\ 2, & otherwise, \end{cases}

for all integers 0 ≤ i < n, and

G(^{−}(C_{5})_{2,i}^{⊏}) = \begin{cases}1, & if i is odd; \\ 3, & otherwise \end{cases} and G(^{⊐}(C_{5})_{2,i}^{⊏}) = \begin{cases}0, & if i is odd; \\ 2, & otherwise \end{cases}

for all integers −1 ≤ i < n. To find G((C_{5})_{2,n}), we exhaust all possible first moves in the Node-Kayles game on (C_{5})_{2,n}. For each 2 ≤ i ≤ n,

G(((C_{5})_{2,n})_{v_{i,0}}) = G((C_{5})_{2,i−2}^{−}) ⊕ G((C_{5})_{2,n−i}^{−})
= \begin{cases}3 ⊕ 1 or 1 ⊕ 3, & if n is odd; \\ 3 ⊕ 3 or 1 ⊕ 1, & otherwise \end{cases}

= \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

for 2 ≤ i ≤ n − 1,

G(((C_{5})_{2,n})_{v_{i,1}}) = G((C_{5})_{2,i−2}^{⊏}) ⊕ G(P_{2}) ⊕ G((C_{5})_{2,n−i−1}^{⊏})

= \begin{cases}2 ⊕ 1 ⊕ 2 or 0 ⊕ 1 ⊕ 0, & if n is odd; \\ 2 ⊕ 1 ⊕ 0 or 0 ⊕ 1 ⊕ 2, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise \end{cases} and

G(((C_{5})_{2,n})_{v_{i,3}}) = G(((C_{5})_{2,n})_{v_{n−i+1,4}}) = G((C_{5})_{2,i−1}^{−}) ⊕ G((C_{5})_{2,n−i−1}^{⊏})
= \begin{cases}3 ⊕ 0 or 1 ⊕ 2, & if n is odd; \\ 3 ⊕ 2 or 1 ⊕ 0, & otherwise \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases}

and for i = 1 or n,

G(((C_{5})_{2,n})_{v_{1,0}}) = G(((C_{5})_{2,n})_{v_{1,4}}) = G(((C_{5})_{2,n})_{v_{n,2}}) = G(((C_{5})_{2,n})_{v_{n,3}})
= G((C_{5})_{2,n−1}^{−})
= \begin{cases}1, & if n is odd; \\ 3, & otherwise \end{cases}

and

G(((C_{5})_{2,n})_{v_{1,1}}) = G(((C_{5})_{2,n})_{v_{1,3}}) = G(((C_{5})_{2,n})_{v_{n,1}}) = G(((C_{5})_{2,n})_{v_{n,4}})
= G(P_{2}) ⊕ G((C_{5})_{2,n−2}^{⊏})
= \begin{cases}1 ⊕ 2, & if n is odd; \\ 1 ⊕ 0, & otherwise \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise. \end{cases}

Therefore,

G((C_{5})_{2,n}) = \begin{cases}mex\{2, 1, 3, 1, 3\}, & if n is odd; \\ mex\{0, 3, 1, 3, 1\}, & otherwise \end{cases} = \begin{cases}0, & if n is odd; \\ 2, & otherwise. \end{cases}

To find G((C_{5})_{2,n}^{−}), we exhaust all possible first moves in the Node-Kayles game on (C_{5})_{2,n}^{−}. For each 2 ≤ i ≤ n,

G(((C_{5})_{2,n}^{−})_{v_{i,0}}) = G((C_{5})_{2,i−2}^{−}) ⊕ G(^{−}(C_{5})_{2,n−i}^{−})
= \begin{cases}3 ⊕ 2 or 1 ⊕ 0, & if n is odd; \\ 3 ⊕ 0 or 1 ⊕ 2, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise, \end{cases}

G(((C_{5})_{2,n}^{−})_{v_{i,1}}) = G((C_{5})_{2,i−2}^{⊏}) ⊕ G(P_{2}) ⊕ G(^{−}(C_{5})_{2,n−i−1}^{⊏})

= \begin{cases}2 ⊕ 1 ⊕ 1 or 0 ⊕ 1 ⊕ 3, & if n is odd; \\ 2 ⊕ 1 ⊕ 3 or 0 ⊕ 1 ⊕ 1, & otherwise \end{cases}

= \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

G(((C_{5})_{2,n}^{−})_{v_{i,3}}) = G((C_{5})_{2,i−1}^{−}) ⊕ G(^{−}(C_{5})_{2,n−i−1}^{⊏})
= \begin{cases}3 ⊕ 3 or 1 ⊕ 1, & if n is odd; \\ 3 ⊕ 1 or 1 ⊕ 3, & otherwise \end{cases}

= \begin{cases}0, & if n is odd; \\ 2, & otherwise, \end{cases}

and

G(((C_{5})_{2,n}^{−})_{v_{i,4}}) = G((C_{5})_{2,i−2}^{⊏}) ⊕ G(^{−}(C_{5})_{2,n−i}^{−})
= \begin{cases}2 ⊕ 2 or 0 ⊕ 0, & if n is odd; \\ 2 ⊕ 0 or 0 ⊕ 2, & otherwise \end{cases}

= \begin{cases}0, & if n is odd; \\ 2, & otherwise, \end{cases}

for i = 1,

G(((C_{5})_{2,n}^{−})_{v_{1,0}}) = G(((C_{5})_{2,n}^{−})_{v_{1,4}}) = G(^{−}(C_{5})_{2,n−1}^{−}) = \begin{cases}2, & if n is odd; \\ 0, & otherwise \end{cases}

and

G(((C_{5})_{2,n}^{−})_{v_{1,1}}) = G(((C_{5})_{2,n}^{−})_{v_{1,3}}) = G(P_{2}) ⊕ G(^{−}(C_{5})_{2,n−2}^{⊏})
= \begin{cases}1 ⊕ 1, & if n is odd; \\ 1 ⊕ 3, & otherwise \end{cases}

= \begin{cases}0, & if n is odd; \\ 2, & otherwise, \end{cases}

and for i = n + 1,

G(((C_{5})_{2,n}^{−})_{v_{n+1,0}}) = G((C_{5})_{2,n−1}^{−}) = \begin{cases}1, & if n is odd; \\ 3, & otherwise \end{cases}

and

G(((C_{5})_{2,n}^{−})_{v_{n+1,1}}) = G((C_{5})_{2,n−1}^{⊏}) = \begin{cases}0, & if n is odd; \\ 2, & otherwise. \end{cases}

Therefore,

G((C_{5})_{2,n}^{−}) = \begin{cases}mex\{1, 2, 0, 0, 2, 0, 1, 0\}, & if n is odd; \\ mex\{3, 0, 2, 2, 0, 2, 3, 2\}, & otherwise \end{cases} = \begin{cases}3, & if n is odd; \\ 1, & otherwise. \end{cases}

To find G((C_{5})_{2,n}^{⊏}), we exhaust all possible first moves in the Node-Kayles game on (C_{5})_{2,n}^{⊏}. For each 2 ≤ i ≤ n + 1,

G(((C_{5})_{2,n}^{⊏})_{v_{i,0}}) = G((C_{5})_{2,i−2}^{−}) ⊕ G(^{−}(C_{5})_{2,n−i}^{⊏})
= \begin{cases}3 ⊕ 3 or 1 ⊕ 1, & if n is odd; \\ 3 ⊕ 1 or 1 ⊕ 3, & otherwise \end{cases}

= \begin{cases}0, & if n is odd; \\ 2, & otherwise, \end{cases}

for 2 ≤ i ≤ n,

G(((C_{5})_{2,n}^{⊏})_{v_{i,1}}) = G((C_{5})_{2,i−2}^{⊏}) ⊕ G(P_{2}) ⊕ G(^{⊐}(C_{5})_{2,n−i−1}^{⊏})

= \begin{cases}2 ⊕ 1 ⊕ 0 or 0 ⊕ 1 ⊕ 2, & if n is odd; \\ 2 ⊕ 1 ⊕ 2 or 0 ⊕ 1 ⊕ 0, & otherwise \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases}

G(((C_{5})_{2,n}^{⊏})_{v_{i,3}}) = G((C_{5})_{2,i−1}^{−}) ⊕ G(^{⊐}(C_{5})_{2,n−i−1}^{⊏})
= \begin{cases}3 ⊕ 2 or 1 ⊕ 0, & if n is odd; \\ 3 ⊕ 0 or 1 ⊕ 2, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise, \end{cases}

and

G(((C_{5})_{2,n}^{⊏})_{v_{i,4}}) = G((C_{5})_{2,i−2}^{⊏}) ⊕ G(^{−}(C_{5})_{2,n−i}^{⊏})
= \begin{cases}2 ⊕ 3 or 0 ⊕ 1, & if n is odd; \\ 2 ⊕ 1 or 0 ⊕ 3, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise, \end{cases}

for i = 1,

G(((C_{5})_{2,n}^{⊏})_{v_{1,0}}) = G(((C_{5})_{2,n}^{⊏})_{v_{1,4}}) = G(^{−}(C_{5})_{2,n−1}^{⊏}) = \begin{cases}3, & if n is odd; \\ 1, & otherwise \end{cases}

and

G(((C_{5})_{2,n}^{⊏})_{v_{1,1}}) = G(((C_{5})_{2,n}^{⊏})_{v_{1,3}}) = G(P_{2}) ⊕ G(^{⊐}(C_{5})_{2,n−2}^{⊏})
= \begin{cases}1 ⊕ 0, & if n is odd; \\ 1 ⊕ 2, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise, \end{cases}

and for i = n + 1,

G(((C_{5})_{2,n}^{⊏})_{v_{n+1,1}}) = G((C_{5})_{2,n−1}^{⊏}) ⊕ G(P_{2})
= \begin{cases}0 ⊕ 1, & if n is odd; \\ 2 ⊕ 1, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise, \end{cases}

G(((C_{5})_{2,n}^{⊏})_{v_{n+1,3}}) = G((C_{5})_{2,n}^{−}) = \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases}

and

G(((C_{5})_{2,n}^{⊏})_{v_{n+1,4}}) = G((C_{5})_{2,n−1}^{⊏}) ⊕ 1
= \begin{cases}0 ⊕ 1, & if n is odd; \\ 2 ⊕ 1, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise. \end{cases}

Therefore,

G((C_{5})_{2,n}^{⊏}) = \begin{cases}mex\{0, 3, 1, 1, 3, 1, 1, 3, 1\}, & if n is odd; \\ mex\{2, 1, 3, 3, 1, 3, 3, 1, 3\}, & otherwise \end{cases} = \begin{cases}2, & if n is odd; \\ 0, & otherwise. \end{cases}

To find G(^{−}(C_{5})_{2,n}^{−}), we exhaust all possible first moves in the Node-Kayles game on −(C_{5})_{2,n}^{−}. For each 2 ≤ i ≤ n,

G((^{−}(C_{5})_{2,n}^{−})_{v_{i,0}}) = G(^{−}(C_{5})_{2,i−2}^{−}) ⊕ G(^{−}(C_{5})_{2,n−i}^{−})
= \begin{cases}0 ⊕ 2 or 2 ⊕ 0, & if n is odd; \\ 0 ⊕ 0 or 2 ⊕ 2, & otherwise \end{cases}

= \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

for 1 ≤ i ≤ n,

G((^{−}(C_{5})_{2,n}^{−})_{v_{i,1}}) = G(^{−}(C_{5})_{2,i−2}^{⊏}) ⊕ G(P_{2}) ⊕ G(^{−}(C_{5})_{2,n−i−1}^{⊏})

= \begin{cases}1 ⊕ 1 ⊕ 1 or 3 ⊕ 1 ⊕ 3, & if n is odd; \\ 1 ⊕ 1 ⊕ 3 or 3 ⊕ 1 ⊕ 1, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise \end{cases}

and

G((^{−}(C_{5})_{2,n}^{−})_{v_{i,3}}) = G((^{−}(C_{5})_{2,n}^{−})_{v_{n−i+1,4}}) = G(^{−}(C_{5})_{2,i−1}^{−}) ⊕ G(^{−}(C_{5})_{2,n−i−1}^{⊏})
= \begin{cases}0 ⊕ 3 or 2 ⊕ 1, & if n is odd; \\ 0 ⊕ 1 or 2 ⊕ 3, & otherwise \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases}

for i = 1 or n + 1,

G((^{−}(C_{5})_{2,n}^{−})_{v_{i,0}}) = G(^{−}(C_{5})_{2,n−1}^{−}) = \begin{cases}2, & if n is odd; \\ 0, & otherwise \end{cases}

and for i = 0 or n + 1,

G((^{−}(C_{5})_{2,n}^{−})_{v_{i,1}}) = G(^{−}(C_{5})_{2,n−1}^{⊏}) = \begin{cases}3, & if n is odd; \\ 1, & otherwise. \end{cases}

Therefore,

G(^{−}(C_{5})_{2,n}^{−}) = \begin{cases}mex\{2, 1, 3, 3, 2, 3\}, & if n is odd; \\ mex\{0, 3, 1, 1, 0, 1\}, & otherwise \end{cases} = \begin{cases}0, & if n is odd; \\ 2, & otherwise. \end{cases}

To find G(^{−}(C_{5})_{2,n}^{⊏}), we exhaust all possible first moves in the Node-Kayles game on −(C_{5})_{2,n}^{⊏}. For each 2 ≤ i ≤ n + 1,

G((^{−}(C_{5})_{2,n}^{⊏})_{v_{i,0}}) = G(^{−}(C_{5})_{2,i−2}^{−}) ⊕ G(^{−}(C_{5})_{2,n−i}^{⊏})
= \begin{cases}0 ⊕ 3 or 2 ⊕ 1, & if n is odd; \\ 0 ⊕ 1 or 2 ⊕ 3, & otherwise \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases}

for 1 ≤ i ≤ n,

G((^{−}(C_{5})_{2,n}^{⊏})_{v_{i,1}}) = G(^{−}(C_{5})_{2,i−2}^{⊏}) ⊕ G(P_{2}) ⊕ G(^{⊐}(C_{5})_{2,n−i−1}^{⊏})

= \begin{cases}1 ⊕ 1 ⊕ 0 or 3 ⊕ 1 ⊕ 2, & if n is odd; \\ 1 ⊕ 1 ⊕ 2 or 3 ⊕ 1 ⊕ 0, & otherwise \end{cases}

= \begin{cases}0, & if n is odd; \\ 2, & otherwise, \end{cases}

G((^{−}(C_{5})_{2,n}^{⊏})_{v_{i,3}}) = G(^{−}(C_{5})_{2,i−1}^{−}) ⊕ G(^{⊐}(C_{5})_{2,n−i−1}^{⊏})
= \begin{cases}0 ⊕ 2 or 2 ⊕ 0, & if n is odd; \\ 0 ⊕ 0 or 2 ⊕ 2, & otherwise \end{cases}

= \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

and

G((^{−}(C_{5})_{2,n}^{⊏})_{v_{i,4}}) = G(^{−}(C_{5})_{2,i−2}^{⊏}) ⊕ G(^{−}(C_{5})_{2,n−i}^{⊏})
= \begin{cases}1 ⊕ 3 or 3 ⊕ 1, & if n is odd; \\ 1 ⊕ 1 or 3 ⊕ 3, & otherwise \end{cases}

= \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

for i = 1,

G((^{−}(C_{5})_{2,n}^{⊏})_{v_{1,0}}) = G(^{−}(C_{5})_{2,n−1}^{⊏}) = \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases}

for i = 0,

G((^{−}(C_{5})_{2,n}^{⊏})_{v_{0,1}}) = G(^{⊐}(C_{5})_{2,n−1}^{⊏}) = \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

and for i = n + 1,

G((^{−}(C_{5})_{2,n}^{⊏})_{v_{n+1,1}}) = G(^{−}(C_{5})_{2,n−1}^{⊏}) ⊕ G(P_{2})
= \begin{cases}3 ⊕ 1, & if n is odd; \\ 1 ⊕ 1, & otherwise \end{cases}

= \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

G((^{−}(C_{5})_{2,n}^{⊏})_{v_{n+1,3}}) = G(^{−}(C_{5})_{2,n}^{−}) = \begin{cases}0, & if n is odd; \\ 2, & otherwise, \end{cases}

and

G((^{−}(C_{5})_{2,n}^{⊏})_{v_{n+1,4}}) = G(^{−}(C_{5})_{2,n−1}^{⊏}) ⊕ 1
= \begin{cases}3 ⊕ 1, & if n is odd; \\ 1 ⊕ 1, & otherwise \end{cases}

= \begin{cases}2, & if n is odd; \\ 0, & otherwise. \end{cases}

Therefore,

G(^{−}(C_{5})_{2,n}^{⊏}) = \begin{cases}mex\{3, 0, 2, 2, 3, 2, 2, 0, 2\}, & if n is odd; \\ mex\{1, 2, 0, 0, 1, 0, 0, 2, 0\}, & otherwise \end{cases} = \begin{cases}1, & if n is odd; \\ 3, & otherwise. \end{cases}

To find G(^{⊐}(C_{5})_{2,n}^{⊏}), we exhaust all possible first moves in the Node-Kayles game on ⊐(C_{5})_{2,n}^{⊏}. For each 1 ≤ i ≤ n + 1,

G((^{⊐}(C_{5})_{2,n}^{⊏})_{v_{i,0}}) = G(^{−}(C_{5})_{2,i−2}^{⊏}) ⊕ G(^{−}(C_{5})_{2,n−i}^{⊏})
= \begin{cases}1 ⊕ 3 or 3 ⊕ 1, & if n is odd; \\ 1 ⊕ 1 or 3 ⊕ 3, & otherwise \end{cases}

= \begin{cases}2, & if n is odd; \\ 0, & otherwise, \end{cases}

for 1 ≤ i ≤ n,

G((^{⊐}(C_{5})_{2,n}^{⊏})_{v_{i,1}}) = G(^{⊐}(C_{5})_{2,i−2}^{⊏}) ⊕ G(P_{2}) ⊕ G(^{⊐}(C_{5})_{2,n−i−1}^{⊏})

= \begin{cases}0 ⊕ 1 ⊕ 0 or 2 ⊕ 1 ⊕ 2, & if n is odd; \\ 0 ⊕ 1 ⊕ 2 or 2 ⊕ 1 ⊕ 0, & otherwise \end{cases}

= \begin{cases}1, & if n is odd; \\ 3, & otherwise \end{cases} and

G((^{⊐}(C_{5})_{2,n}^{⊏})_{v_{i,3}}) = G((^{⊐}(C_{5})_{2,n}^{⊏})_{v_{n−i+1,4}}) = G(^{−}(C_{5})_{2,i−1}^{⊏}) ⊕ G(^{⊐}(C_{5})_{2,n−i−1}^{⊏})
= \begin{cases}1 ⊕ 2 or 3 ⊕ 0, & if n is odd; \\ 1 ⊕ 0 or 3 ⊕ 2, & otherwise \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases}

for i = 0 or n + 1,

G((^{⊐}(C_{5})_{2,n}^{⊏})_{v_{i,1}}) = G(P_{2}) ⊕ G(^{⊐}(C_{5})_{2,n−1}^{⊏})
= \begin{cases}1 ⊕ 2, & if n is odd; \\ 1 ⊕ 0, & otherwise, \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases}

G((^{⊐}(C_{5})_{2,n}^{⊏})_{v_{0,3}}) = G((^{⊐}(C_{5})_{2,n}^{⊏})_{v_{n+1,4}}) = 1 ⊕ G(^{⊐}(C_{5})_{2,n−1}^{⊏})
= \begin{cases}1 ⊕ 2, & if n is odd; \\ 1 ⊕ 0, & otherwise, \end{cases}

= \begin{cases}3, & if n is odd; \\ 1, & otherwise, \end{cases}

and

G((^{⊐}(C_{5})_{2,n}^{⊏})_{v_{0,4}}) = G((^{⊐}(C_{5})_{2,n}^{⊏})_{v_{n+1,3}}) = G(^{−}(C_{5})_{2,n}^{⊏}) = \begin{cases}1, & if n is odd; \\ 3, & otherwise. \end{cases}

Therefore,

G(^{⊐}(C_{5})_{2,n}^{⊏}) = \begin{cases}mex\{2, 1, 3, 3, 3, 1\}, & if n is odd; \\ mex\{0, 3, 1, 1, 1, 3\}, & otherwise \end{cases} = \begin{cases}0, & if n is odd; \\ 2, & otherwise. \end{cases}

To study the Nimber sequence (G((C_{4})_{1,n}) : n ∈ ℕ), we need to further define two related families of graphs. The first variation, denoted by (C_{4})_{1,n}^{∨}, is a (1, n)-linked 4-cycle with additional vertices v_{n+1,2} and v_{n+1,3} and an additional path v_{n,1}v_{n+1,3}v_{n+1,2}; the second variation, denoted by ^{∨}(C_{4})_{1,n}^{∨}, is the first variation (C_{4})_{1,n}^{∨} with additional vertices v_{0,2} and v_{0,3} and an additional path v_{1,0}v_{0,2}v_{0,3}. Figures 23 and 24 are examples of the first and second variations of a (1, n)-linked 4-cycle, respectively.

\begin{matrix}v_{1,0} \\ v_{1,1} = v_{2,0} \\ v_{1,2} \\ v_{1,3} \\ v_{2,1} = v_{3,0} \\ v_{2,2} \\ v_{2,3} \\ v_{3,1} = v_{4,0} \\ v_{3,2} \\ v_{3,3} \\ v_{4,1} = v_{5,0} \\ v_{4,2} \\ v_{4,3} \\ v_{5,1} = v_{6,0} \\ v_{5,2} \\ v_{5,3} \\ v_{6,1} = v_{7,0} \\ v_{6,2} \\ v_{6,3} \\ v_{7,2} \\ v_{7,3} \end{matrix}

Figure 23: The first variation of the (1, 6)-linked 4-cycle (C_{4})_{1,6}^{∨}

\begin{matrix}v_{0,2} \\ v_{0,3} \\ v_{0,1} = v_{1,0} \\ v_{1,1} = v_{2,0} \\ v_{1,2} \\ v_{1,3} \\ v_{2,1} = v_{3,0} \\ v_{2,2} \\ v_{2,3} \\ v_{3,1} = v_{4,0} \\ v_{3,2} \\ v_{3,3} \\ v_{4,1} = v_{5,0} \\ v_{4,2} \\ v_{4,3} \\ v_{5,1} = v_{6,0} \\ v_{5,2} \\ v_{5,3} \\ v_{6,1} = v_{7,0} \\ v_{6,2} \\ v_{6,3} \\ v_{7,2} \\ v_{7,3} \end{matrix}

Figure 24: The second variation of the (1, 6)-linked 4-cycle ^{∨}(C_{4})_{1,6}^{∨}

It is also convenient to extend the definition of (C_{4})_{1,n} to the case when n = 0, the definition of (C_{4})_{1,n}^{∨} to the cases when −1 ≤ n ≤ 0, as well as the definition of ^{∨}(C_{4})_{1,n}^{∨} to the cases when −2 ≤ n ≤ 0 and determine the corresponding Nimbers as follows.

n (C_{4})_{1,n} G((C_{4})_{1,n}) (C_{4})_{1,n}^{∨} G((C_{4})_{1,n}^{∨}) ^{∨}(C_{4})_{1,n}^{∨} G(^{∨}(C_{4})_{1,n}^{∨})
−2 N/A  N/A  N/A  N/A  ∅  0
−1 N/A  N/A  ∅  0  1
0  1  2  3

Theorem 9. The Nimber sequences (G((C_{4})_{1,n}) : n ∈ ℕ), (G((C_{4})_{1,n}^{∨}) : n ∈ ℕ), and (G(^{∨}(C_{4})_{1,n}^{∨}) : n ∈ ℕ) satisfy recursions

G((C_{4})_{1,n}) = mex ({G((C_{4})_{1,i−3}^{∨}) ⊕ G((C_{4})_{1,n−i−1}^{∨}) : 2 ≤ i ≤ n}
∪ {G((C_{4})_{1,i−1}) ⊕ G((C_{4})_{1,n−i−1}^{∨}) : 1 ≤ i ≤ n}),
G((C_{4})_{1,n}^{∨}) = mex ({G((C_{4})_{1,i−3}^{∨}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}) : 2 ≤ i ≤ n}
∪ {G((C_{4})_{1,i−1}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}),
G((C_{4})_{1,i−2}^{∨}) ⊕ G((C_{4})_{1,n−i}^{∨}) : 1 ≤ i ≤ n}),

and

G(^{∨}(C_{4})_{1,n}^{∨}) = mex ({G(^{∨}(C_{4})_{1,i−3}^{∨}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}) : 1 ≤ i ≤ n + 1}
∪ {G((C_{4})_{1,i−1}^{∨}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}) : 0 ≤ i ≤ n + 1}).

Proof. For each positive integer n, to find G((C_{4})_{1,n}), we exhaust all possible first moves in the Node-Kayles game on (C_{4})_{1,n}. For each 2 ≤ i ≤ n,

G(((C_{4})_{1,n})_{v_{i,0}}) = G((C_{4})_{1,i−3}^{∨}) ⊕ 1 ⊕ 1 ⊕ G((C_{4})_{1,n−i−1}^{∨}) = G((C_{4})_{1,i−3}^{∨}) ⊕ G((C_{4})_{1,n−i−1}^{∨}), for 1 ≤ i ≤ n,

G(((C_{4})_{1,n})_{v_{i,2}}) = G(((C_{4})_{1,n})_{v_{n−i+1,3}}) = G((C_{4})_{1,i−1}) ⊕ G((C_{4})_{1,n−i−1}^{∨}),

and for i = 1 or n,

G(((C_{4})_{1,n})_{v_{1,0}}) = G(((C_{4})_{1,n})_{v_{n,1}}) = G((C_{4})_{1,0}) ⊕ G((C_{4})_{1,n−2}^{∨}).

Therefore,

G((C_{4})_{1,n}) = mex ({G((C_{4})_{1,i−3}^{∨}) ⊕ G((C_{4})_{1,n−i−1}^{∨}) : 2 ≤ i ≤ n}
∪ {G((C_{4})_{1,i−1}) ⊕ G((C_{4})_{1,n−i−1}^{∨}) : 1 ≤ i ≤ n}).

To find G((C_{4})_{1,n}^{∨}), we exhaust all possible first moves in the Node-Kayles game on (C_{4})_{1,n}^{∨}. For each 2 ≤ i ≤ n + 1, G(((C_{4})_{1,n}^{∨})_{v_{i,0}}) = G((C_{4})_{1,i−3}^{∨}) ⊕ 1 ⊕ 1 ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}) = G((C_{4})_{1,i−3}^{∨}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}), for 1 ≤ i ≤ n + 1,

G(((C_{4})_{1,n}^{∨})_{v_{i,2}}) = G((C_{4})_{1,i−1}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨})

and

G(((C_{4})_{1,n}^{∨})_{v_{i,3}}) = G((C_{4})_{1,i−2}^{∨}) ⊕ G((C_{4})_{1,n−i}^{∨}),

and for i = 1,

G(((C_{4})_{1,n}^{∨})_{v_{1,0}}) = G((C_{4})_{1,0}) ⊕ G(^{∨}(C_{4})_{1,n−2}^{∨}).

Therefore,

G((C_{4})_{1,n}^{∨}) = mex ({G((C_{4})_{1,i−3}^{∨}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}) : 2 ≤ i ≤ n + 1}
∪ {G((C_{4})_{1,i−1}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}),
G((C_{4})_{1,i−2}^{∨}) ⊕ G((C_{4})_{1,n−i}^{∨}) : 1 ≤ i ≤ n + 1}).

Finally, to find G(^{∨}(C_{4})_{1,n}^{∨}), we exhaust all possible first moves in the Node-Kayles game on ^{∨}(C_{4})_{1,n}^{∨}. For each 1 ≤ i ≤ n + 1,

G((^{∨}(C_{4})_{1,n}^{∨})_{v_{i,0}}) = G(^{∨}(C_{4})_{1,i−3}^{∨}) ⊕ 1 ⊕ 1 ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨})
= G(^{∨}(C_{4})_{1,i−3}^{∨}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}),

and for 0 ≤ i ≤ n + 1,

G((^{∨}(C_{4})_{1,n}^{∨})_{v_{i,2}}) = G((^{∨}(C_{4})_{1,n}^{∨})_{v_{n−i+1,3}}) = G((C_{4})_{1,i−1}^{∨}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}).

Therefore,

G(^{∨}(C_{4})_{1,n}^{∨}) = mex ({G(^{∨}(C_{4})_{1,i−3}^{∨}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}) : 1 ≤ i ≤ n + 1}
∪ {G((C_{4})_{1,i−1}^{∨}) ⊕ G(^{∨}(C_{4})_{1,n−i−1}^{∨}) : 0 ≤ i ≤ n + 1}).

With the recursions given by Theorem 9, we can easily compute the first 100, 000 terms in the Nimber sequence (G((C_{4})_{1,n}) : n ∈ ℕ), which is now listed on the OEIS as \underline{A316629} [7]. Note that sequence (G((C_{4})_{1,n}) : n ∈ ℕ) does not seem to be periodic, nor are we able to find a closed form. It is mildly surprising that the Nimber sequences of the Node-Kayles game on linked 4-cycles differ so drastically by changing the link vertices.

We finish this section with our study on the Nimber sequence of linked diamonds. A diamond is formed by adding an additional diagonal edge to a 4-cycle, i.e., a diamond has vertex set {v_{0}, v_{1}, v_{2}, v_{3}} and edge set {v_{0}v_{1}, v_{1}v_{2}, v_{2}v_{3}, v_{3}v_{0}, v_{0}v_{2}}. To form an n-linked diamond D_{n}, we begin with a collection of n diamonds with vertex sets {v_{i,0}, v_{i,1}, v_{i,2}, v_{i,3}} for 1 ≤ i ≤ n, and we identify vertices such that v_{i,2} = v_{i+1,0} for all 1 ≤ i ≤ n − 1. The vertex v_{n,2} will also be called v_{n+1,0}.

\begin{matrix}v_{1,0} \\ v_{1,1} \\ v_{1,2} \\ v_{1,3} \\ v_{2,0} \\ v_{2,1} \\ v_{2,2} \\ v_{2,3} \\ v_{3,0} \\ v_{3,1} \\ v_{3,2} \\ v_{3,3} \\ v_{4,0} \\ v_{4,1} \\ v_{4,2} \\ v_{4,3} \\ v_{5,0} \\ v_{5,1} \\ v_{5,2} \\ v_{5,3} \end{matrix}

\begin{matrix}v_{1,3} \\ v_{1,1} \\ v_{2,3} \\ v_{2,1} \\ v_{3,3} \\ v_{3,1} \\ v_{4,3} \\ v_{4,1} \\ v_{5,3} \\ v_{5,1} \\ v_{1,0} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \end{matrix}

Figure 25: Linking 5 diamonds (top) as D_{5} (bottom)

If we try to link n diamonds after rotating each of them by 90 degrees, we will obtain a 2n-chained clique that chains up 2n copies of K_{3}, which was studied in Section 4. Hence, we do not consider the graph in Figure 26 as a linked diamond.

\begin{matrix}v_{1,0} \\ v_{1,2} \\ v_{2,0} \\ v_{2,2} \\ v_{3,0} \\ v_{3,2} \\ v_{4,0} \\ v_{4,2} \\ v_{5,0} \\ v_{5,2} \\ v_{1,1} \\ v_{1,3} = v_{2,1} \\ v_{2,3} = v_{3,1} \\ v_{3,3} = v_{4,1} \\ v_{4,3} = v_{5,1} \\ v_{5,3} \end{matrix}

Figure 26: A 2n-chained clique CK_{2n}

To study the Nimber sequence (G(D_{n}) : n ∈ ℕ), we need to further define two related families of graphs. The first variation, denoted by D_{n}^{<}, is an n-linked diamond with additional vertices v_{n+1,1} and v_{n+1,3} and additional edges v_{n,2}v_{n+1,1} and v_{n,2}v_{n+1,3}; the second variation, denoted by^{>}D_{n}^{<}, is the first variation D_{n}^{<} with additional vertices v_{0,1} and v_{0,3} and additional edges v_{0,1}v_{1,0} and v_{0,3}v_{1,0}. Figures 27 and 28 are examples of the first and second variations of an n-linked diamond, respectively.

\begin{matrix}v_{1,3} \\ v_{1,1} \\ v_{2,3} \\ v_{2,1} \\ v_{3,3} \\ v_{3,1} \\ v_{4,3} \\ v_{4,1} \\ v_{5,3} \\ v_{5,1} \\ v_{6,3} \\ v_{6,1} \\ v_{7,3} \\ v_{7,1} \\ v_{1,0} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \end{matrix}

Figure 27: The first variation of the 6-linked diamond D_{6}^{<}

\begin{matrix}v_{0,3} \\ v_{0,1} \\ v_{1,3} \\ v_{1,1} \\ v_{2,3} \\ v_{2,1} \\ v_{3,3} \\ v_{3,1} \\ v_{4,3} \\ v_{4,1} \\ v_{5,3} \\ v_{5,1} \\ v_{6,3} \\ v_{6,1} \\ v_{7,3} \\ v_{7,1} \\ v_{1,0} \\ v_{1,2} = v_{2,0} \\ v_{2,2} = v_{3,0} \\ v_{3,2} = v_{4,0} \\ v_{4,2} = v_{5,0} \\ v_{5,2} = v_{6,0} \\ v_{6,2} = v_{7,0} \end{matrix}

Figure 28: The second variation of the 6-linked diamond ^{>}D_{6}^{<}

It is also convenient to extend the definitions of D_{n}^{<} and ^{>}D_{n}^{<} to the cases when −2 ≤ n ≤ 0 and determine the corresponding Nimbers as follows.

n D_{n}^{<} G(D_{n}^{<}) ^{>}D_{n}^{<} G(^{>}D_{n}^{<})
−2 ∅  0  ∅  0
−1 ∅  0  0

0  2  2

To simplify the notation, we define a(n) = G(D_{n}), b(n) = G(D_{n}^{<}), and c(n) = G(^{>}D_{n}^{<}). The sequence (a(n) : n ∈ ℕ) is now listed on the OEIS as \underline{A316781} [7].

Theorem 10. The Nimber sequences (a(n) : n ≥ 69), (b(n) : n ≥ 69), and (c(n) : n ≥ 69) are periodic with period 12.

Proof. By the symmetry of ^{>}D_{n}^{<}, we have

c(n) = mex ({G((^{>}D_{n}^{<})_{v_{i,0}}) : 1 ≤ i ≤ ⌈(n + 1)/2⌉} ∪ {G((^{>}D_{n}^{<})_{v_{i,1}}) : 0 ≤ i ≤ ⌊(n + 1)/2⌋}).

It is easy to see that

G((^{>}D_{n}^{<})_{v_{i,0}}) = G(^{>}D_{i−3}^{<}) ⊕ G(^{>}D_{n−i−1}^{<})

and

G((^{>}D_{n}^{<})_{v_{i,1}}) = G(^{>}D_{i−2}^{<}) ⊕ 1 ⊕ G(^{>}D_{n−i−1}^{<}),

so

c(n) = mex ({c(i − 3) ⊕ c(n − i − 1) : 1 ≤ i ≤ ⌈(n + 1)/2⌉}
∪ {c(i − 2) ⊕ 1 ⊕ c(n − i − 1) : 0 ≤ i ≤ ⌊(n + 1)/2⌋})  (5)

for all n ∈ ℕ. Now, we are ready to prove that (c(n) : n ≥ 69) is periodic with period 12 by strong induction.

With recursion (5), together with the initial conditions (c(−2), c(−1), c(0)) = (0, 0, 2), we can compute the values of the sequence (c(n) : 1 ≤ n ≤ 175), which is periodic with period 12 when 69 ≤ n ≤ 175. Assume that for some n ≥ 176, c(i) = c(i − 12) for all 81 ≤ i < n.

Then

c(n) = mex ({c(i − 3) ⊕ c(n − i − 1) : 1 ≤ i ≤ ⌈(n + 1)/2⌉ − 6}
∪ {c(i − 3) ⊕ c(n − i − 1) : ⌈(n + 1)/2⌉ − 5 ≤ i ≤ ⌈(n + 1)/2⌉}
∪ {c(i − 2) ⊕ 1 ⊕ c(n − i − 1) : 0 ≤ i ≤ ⌊(n + 1)/2⌋ − 6}
∪ {c(i − 2) ⊕ 1 ⊕ c(n − i − 1) : ⌊(n + 1)/2⌋ − 5 ≤ i ≤ ⌊(n + 1)/2⌋})
= mex ({c(i − 3) ⊕ c((n − 12) − i − 1) : 1 ≤ i ≤ ⌈((n − 12) + 1)/2⌉}
∪ {c(i − 3) ⊕ c((n − 12) − i − 1) : ⌈(n + 1)/2⌉ − 5 ≤ i ≤ ⌈(n + 1)/2⌉}
∪ {c(i − 2) ⊕ 1 ⊕ c((n − 12) − i − 1) : 0 ≤ i ≤ ⌊((n − 12) + 1)/2⌋}
∪ {c(i − 2) ⊕ 1 ⊕ c((n − 12) − i − 1) : ⌊(n + 1)/2⌋ − 5 ≤ i ≤ ⌊(n + 1)/2⌋})
= mex ({c(i − 3) ⊕ c((n − 12) − i − 1) : 1 ≤ i ≤ ⌈((n − 12) + 1)/2⌉}
∪ {c(i − 3) ⊕ c((n − 12) − i − 1) : ⌈(n + 1)/2⌉ − 17 ≤ i ≤ ⌈(n + 1)/2⌉ − 12}
∪ {c(i − 2) ⊕ 1 ⊕ c((n − 12) − i − 1) : 0 ≤ i ≤ ⌊((n − 12) + 1)/2⌋}
∪ {c(i − 2) ⊕ 1 ⊕ c((n − 12) − i − 1) : ⌊(n + 1)/2⌋ − 17 ≤ i ≤ ⌊(n + 1)/2⌋ − 12})
= mex ({c(i − 3) ⊕ c((n − 12) − i − 1) : 1 ≤ i ≤ ⌈((n − 12) + 1)/2⌉}
∪ {c(i − 2) ⊕ 1 ⊕ c((n − 12) − i − 1) : 0 ≤ i ≤ ⌊((n − 12) + 1)/2⌋})
= c(n − 12),

which completes our induction.

Next, we study b(n). By the symmetry of D_{n}^{<}, we have

b(n) = mex{G((D_{n}^{<})_{v_{i,0}}), G((D_{n}^{<})_{v_{i,1}}) : 1 ≤ i ≤ n + 1}.

It is easy to see that

G((D_{n}^{<})_{v_{i,0}}) = G(D_{i−3}^{<}) ⊕ G(^{>}D_{n−i−1}^{<})

and

G((D_{n}^{<})_{v_{i,1}}) = G(D_{i−2}^{<}) ⊕ 1 ⊕ G(^{>}D_{n−i−1}^{<}),

so

b(n) = mex{b(i − 3) ⊕ c(n − i − 1), b(i − 2) ⊕ 1 ⊕ c(n − i − 1) : 1 ≤ i ≤ n + 1} (6)

for all n ∈ ℕ. Now, we are ready to prove that (b(n) : n ≥ 69) is periodic with period 12 by strong induction.

With recursion (6), together with the initial conditions (b(−2), b(−1), b(0)) = (0, 0, 2) and the sequence (c(n) : n ∈ ℕ), we can compute the values of the sequence (b(n) : 1 ≤ n ≤ 164), which is periodic with period 12 when 69 ≤ n ≤ 164. Assume that for some n ≥ 165, b(i) = b(i − 12) for all 81 ≤ i < n. Then

b(n) = mex ({b(i − 3) ⊕ c(n − i − 1), b(i − 2) ⊕ 1 ⊕ c(n − i − 1) : 1 ≤ i ≤ n − 82}

∪ {b(i − 3) ⊕ c(n − i − 1), b(i − 2) ⊕ 1 ⊕ c(n − i − 1) : n − 81 ≤ i ≤ n + 1})

= mex ({b(i − 3) ⊕ c((n − 12) − i − 1), b(i − 2) ⊕ 1 ⊕ c((n − 12) − i − 1) :
1 ≤ i ≤ n − 82}
∪ {b(i − 3) ⊕ c((n − 12) − i − 1), b(i − 2) ⊕ 1 ⊕ c((n − 12) − i − 1) :
n − 93 ≤ i ≤ n − 11})
= mex{b(i − 3) ⊕ c((n − 12) − i − 1), b(i − 2) ⊕ 1 ⊕ c((n − 12) − i − 1) :
1 ≤ i ≤ (n − 12) + 1}
= b(n − 12),

which completes our induction.

Finally, we study a(n). By the symmetry of D_{n}, we have

a(n) = mex ({G((D_{n})_{v_{i,0}}) : 1 ≤ i ≤ ⌈(n + 1)/2⌉} ∪ {G((D_{n})_{v_{i,1}}) : 1 ≤ i ≤ ⌊(n + 1)/2⌋}).

It is easy to see that

G((D_{n})_{v_{i,0}}) = G(D_{i−3}^{<}) ⊕ G(D_{n−i−1}^{<})

and

G((D_{n})_{v_{i,1}}) = G(D_{i−2}^{<}) ⊕ 1 ⊕ G(D_{n−i−1}^{<}),

so

a(n) = mex ({b(i − 3) ⊕ b(n − i − 1) : 1 ≤ i ≤ ⌈(n + 1)/2⌉}
∪ {b(i − 2) ⊕ 1 ⊕ b(n − i − 1) : 1 ≤ i ≤ ⌊(n + 1)/2⌋})  (7)

for all n ∈ ℕ. Now, we are ready to prove that (a(n) : a ≥ 69) is periodic with period 12 by strong induction.

With recursion (7), together with the sequence (b(n) : n ∈ ℕ), we can compute the values of the sequence (a(n) : 1 ≤ n ≤ 175), which is periodic with period 12 when 69 ≤ n ≤ 175.

Assume that for some n ≥ 176, a(i) = a(i − 12) for all 81 ≤ i < n. Then

a(n) = mex ({b(i − 3) ⊕ b(n − i − 1) : 1 ≤ i ≤ ⌈(n + 1)/2⌉ − 6}
∪ {b(i − 3) ⊕ b(n − i − 1) : ⌈(n + 1)/2⌉ − 5 ≤ i ≤ ⌈(n + 1)/2⌉}
∪ {b(i − 2) ⊕ 1 ⊕ b(n − i − 1) : 1 ≤ i ≤ ⌊(n + 1)/2⌋ − 6}
∪ {b(i − 2) ⊕ 1 ⊕ b(n − i − 1) : ⌊(n + 1)/2⌋ − 5 ≤ i ≤ ⌊(n + 1)/2⌋})
= mex ({b(i − 3) ⊕ b((n − 12) − i − 1) : 1 ≤ i ≤ ⌈((n − 12) + 1)/2⌉}
∪ {b(i − 3) ⊕ b((n − 12) − i − 1) : ⌈(n + 1)/2⌉ − 5 ≤ i ≤ ⌈(n + 1)/2⌉}
∪ {b(i − 2) ⊕ 1 ⊕ b((n − 12) − i − 1) : 1 ≤ i ≤ ⌊((n − 12) + 1)/2⌋}

∪ {b(i − 2) ⊕ 1 ⊕ b((n − 12) − i − 1) : ⌊(n + 1)/2⌋ − 5 ≤ i ≤ ⌊(n + 1)/2⌋})

= mex ({b(i − 3) ⊕ b((n − 12) − i − 1) : 1 ≤ i ≤ ⌈((n − 12) + 1)/2⌉}

∪ {b(i − 3) ⊕ b((n − 12) − i − 1) : ⌈(n + 1)/2⌉ − 17 ≤ i ≤ ⌈(n + 1)/2⌉ − 12}

∪ {b(i − 2) ⊕ 1 ⊕ b((n − 12) − i − 1) : 1 ≤ i ≤ ⌊((n − 12) + 1)/2⌋}

∪ {b(i − 2) ⊕ 1 ⊕ b((n − 12) − i − 1) : ⌊(n + 1)/2⌋ − 17 ≤ i ≤ ⌊(n + 1)/2⌋ − 12})

= mex ({b(i − 3) ⊕ b((n − 12) − i − 1) : 1 ≤ i ≤ ⌈((n − 12) + 1)/2⌉}
∪ {b(i − 2) ⊕ 1 ⊕ b((n − 12) − i − 1) : 1 ≤ i ≤ ⌊((n − 12) + 1)/2⌋})
= a(n − 12),

which completes our induction.

By computation, we further discover that the sequences (a(n) : n ≥ 4), (b(n) : n ≥ 4), (c(n) : n ≥ 4) are identical, and their repeating unit (a(n) : 69 ≤ n ≤ 80) is given by

7, 5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2.

In particular, the maximum Nimber value is 8, occurring at a(25), a(31), a(43), a(49), and a(61 + 6k) for all nonnegative integers k. Also, a(n) = 0 if and only if n = 3 or

n ≡ 11 (mod 12).

It is worth mentioning that the Nimber sequence (c(n) : n ≥ −1) is precisely the Nimber sequence for the “Remove-a-Square game” on an n × 2 rectangle, listed on the OEIS as \underline{A286332} [7]. The Remove-a-Square game on an n × 2 rectangle is also an impartial game, where two players alternate to remove a 1 × 1 or a 2 × 2 square from the n × 2 rectangle. If we label the 1 × 1 squares by s_{i,j} for 0 ≤ i ≤ n − 1 and j ∈ {1, 3}, then we can easily see that removing the 1×1 square s_{i,j} is equivalent to removing N_{(^{>}D_{n−2}^{<})}[v_{i,j}], and removing the 2×2 square composed of s_{i,1}, s_{i,3}, s_{i+1,1}, s_{i+1,3} is equivalent to removing N_{(^{>}D_{n−2}^{<})}[v_{i+1,0}]. Therefore, the Remove-a-Square game on an n × 2 rectangle is equivalent to the Node-Kayles game on >D_{n−2}^{<}, thus the Nimber sequence (c(n) : n ≥ −1) is the same as the Nimber sequence for the Remove-a-Square game on an n × 2 rectangle.

6 Nimbers of the Node-Kayles game on other graphs and concluding remarks

In the previous sections, we studied the Nimbers of the Node-Kayles game on 3-paths, lattice graphs, prism graphs, chained cliques, linked cliques, linked cycles, and linked diamonds. There are many other interesting families of graphs for us to examine. Two such families are hypercubes and generalized Petersen graphs. An n-dimensional hypercube, denoted by Q_{n}, is a graph with the vertex set {0, 1}^{n}, and between any two vertices (x_{1}, x_{2}, …, x_{n}) and (y_{1}, y_{2}, …, y_{n}) in {0, 1}^{n}, there is an edge if and only if ∑_{i=1}^{n} |x_{i} − y_{i}| = 1.

Theorem 11. The Nimber G(Q_{n}) is 1 if n = 1 and is 0 otherwise.

Proof. When n = 1, Q_{1} is isomorphic to the path P_{2}, so G(Q_{1}) = 1. When n > 1, let φ be a graph homomorphism on Q_{n} such that φ(x_{1}, x_{2}, …, x_{n}) = (1 − x_{1}, 1 − x_{2}, …, 1 − x_{n}). Essentially, φ reflects the hypercube about the center of the hypercube. It is easy to check that φ is an involution that satisfies the condition in Theorem 4, so G(Q_{n}) = 0.

For each integer n ≥ 5, a generalized Petersen graph, denoted by GP (n, 2), is a graph with the vertex set {u_{0}, u_{1}, …, u_{n−1}, v_{0}, v_{1}, …, v_{n−1}} and the edge set {u_{i}u_{i+1}, u_{i}v_{i}, v_{i}v_{i+2} : 1 ≤ i ≤ n}, where addition in the indices is performed modulo n. The first twenty terms in the Nimber sequence (G(GP (n, 2)) : n ≥ 5) are calculated and now listed on the OEIS as \underline{A316533} [7]. In general, we can determine the Nimber G(GP (n, 2)) when n is even, due to the following theorem.

Theorem 12. The Nimber G(GP (n, 2)) is 0 if n is even.

Proof. Let n = 2k for some integer k ≥ 3. For any vertex w ∈ V (GP (n, 2)), let φ be a graph homomorphism on GP (n, 2) such that

φ(w) = \begin{cases}v_{i+n/2}, & if w = v_{i}; \\ u_{i+n/2}, & if w = u_{i}, \end{cases}

where addition in the indices is performed modulo n. Essentially, φ rotates the generalized Petersen graph by 180^{∘}. It is easy to check that φ is an involution that satisfies the condition in Theorem 4, so G(GP (2k, 2)) = 0.

We are unable to determine any explicit formula or recursion for the odd terms of this sequence at the moment, and this is one of our future goals. Additional goals include expanding the results of Sections 3 and 5. For example, our technique of studying the recursion will work for determining the Nimber sequence of (3, n)-linked 6-cycle, but it will not work for other linked cycles, such as (1, n)-linked 5-cycle, since removing a vertex no longer necessarily disconnects a component. It is in our interest to discover other techniques for determining the Nimber sequence of (1, n)-linked 5-cycle and other graphs that we fail to handle at the moment, such as the n × 3 lattice graph or all lattice graphs in general.

Furthermore, as mentioned in Section 5, the Nimber sequence of (1, n)-linked 4-cycle does not seem to be periodic. Another seemingly nonperiodic Nimber sequence is for the Node-Kayles game on the square of paths, namely (G((P_{n})^{2}) : n ∈ ℕ). However, there is an important open conjecture by Richard Guy that the Nimber sequences of all octal games are periodic. As we have shown in this paper, there are many connections between Node-Kayles games and octal games, so we would like to prove or disprove the periodicity of these Nimber sequences.

References

[1] H. L. Bodlaender and D. Kratsch, Kayles and Nimbers, J. Algorithms 43 (2002), 106– 119.

[2] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, A. K. Peters, 2001.

[3] E. Duchêne, S. Gravier, and M. Mhalla, Combinatorial graph games, Ars. Combin. 90 (2009), 33–44.

[4] H. E. Dudeney, The Canterbury Puzzles, London, 1910.

[5] A. Guignard and É. Sopena, Compound Node-Kayles on paths, Theoret. Comput. Sci. 410 (2009), 2033–2044.

[6] S. Loyd, Cyclopedia of Tricks and Puzzles, New York, 1914.

[7] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

    at https://oeis.org.

2010 Mathematics Subject Classification: Primary 91A46; Secondary 91A43, 05C57, 11Y55. Keywords: Node-Kayles, Domination game, Sprague-Grundy, Nimber sequence, octal game, graph involution, periodic.

(Concerned with sequences \underline{A002186}, \underline{A002187}, \underline{A071426}, \underline{A071441}, \underline{A071461}, \underline{A286332}, \underline{A316533}, \underline{A316629}, \underline{A316632}, \underline{A316781}, and \underline{A317367}.)

Received November 10 2019; revised version received March 11 2020. Published in Journal of Integer Sequences, March 16 2020.

Return to Journal of Integer Sequences home page.