Journal of Integer Sequences, Vol. 23 (2020), Article 20.3.5

Nimber Sequences of Node-Kayles Games


Sierra Brown
Department of Mathematics
Creighton University
2500 California Plaza
Omaha, NE 68178
USA

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

Eugene Fiorini
Department of Mathematics
Muhlenberg College
2400 Chew Street
Allentown, PA 18104
USA

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

Diego Manzano-Ruiz
Department of Mathematics
Kutztown University of Pennsylvania
15200 Kutztown Road
Kutztown, PA 19530
USA

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

Riley Waechter
Department of Mathematics and Statistics
Northern Arizona University
801 South Osborne Drive
Flagstaff, AZ 86011
USA

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

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.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A002186 A002187 A071426 A071441 A071461 A286332 A316533 A316629 A316632 A316781 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