login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 25 19:21 EDT 2023. Contains 361528 sequences. (Running on oeis4.)