Nimber Sequences of Node-Kayles Games

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

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