|
| |
|
|
A316533
|
|
a(n) is the Sprague-Grundy value of the Node-Kayles game played on the generalized Petersen graph P(n,2).
|
|
3
|
|
|
|
1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
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.
|
|
|
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.
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
a(25)-a(26) from Max Fan, May 23 2021
|
|
|
STATUS
|
approved
|
| |
|
|
