A316533 a(n) is the Sprague-Grundy value of the Node-Kayles game played on the generalized Petersen graph P(n,2).

1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0

Offset

5

Comments

For all values of n, the Sprague-Grundy values of the Node-Kayles game played on the generalized Petersen graph P(n,2) cannot be greater than 2 since there exist only 2 non-isomorphic first moves.

Furthermore, for all even values of n, the generalized Petersen graph P(n,2) has an automorphism defined by a rotation of 180 degrees. Hence, for every move by player 1, player 2 can respond by coloring the orbit-equivalent point of player 1's move. Thus, the Sprague-Grundy value of the Node-Kayles game played on P(n,2) is 0 when n is even.

References

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

Links

Table of n, a(n) for n=5..26.

Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Diego Manzano-Ruiz, Sean Rainville, Riley Waechter, and Tony W. H. Wong, Nimber Sequences of Node-Kayles Games, J. Int. Seq., Vol. 23 (2020), Article 20.3.5.

Max Fan, Generalized Node-Kayles calculator implemented in Rust

Riley S. Waechter, Python program for A316533

Example

For n=5, a(5) is the Sprague-Grundy value of the Node-Kayles game played on the Petersen graph. Since the Petersen graph is vertex transitive, all first moves are isomorphic. After the first move, the resultant graph is the cycle C_6. The Sprague-Grundy value of the Node-Kayles game played on C_6 is 0. Hence, a(5) = mex{0} = 1, where mex is the minimum excluded function.

Prog

(Rust) // See Fan link. - Max Fan, May 23 2021

Crossrefs

Cf. A002186, A002187 for the Sprague-Grundy values of the Node-Kayles games on other graphs.

Sequence in context: A171894 A284957 A357385 * A085405 A036988 A108357

Adjacent sequences: A316530 A316531 A316532 * A316534 A316535 A316536

Keyword

nonn,more

Author

Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Sean E. Rainville, Riley S. Waechter, Wing Hong Tony Wong, Jul 13 2018

Extensions

a(25)-a(26) from Max Fan, May 23 2021

Status

approved