Journal of Integer Sequences, Vol. 24 (2021), Article 21.6.4

Characterizing Winning Positions in the Impartial Two-Player Pebbling Game on Complete Graphs

Eugene Fiorini
Rutgers University
96 Frelinghuysen Road
Piscataway, NJ 08854

Max Lind
University Scholars Program
Pennsylvania Leadership Charter School
1585 Paoli Pike
West Chester, PA 19380

Andrew Woldar
Department of Mathematics & Statistics
Villanova University
800 Lancaster Avenue
Villanova, PA 19085

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


A pebbling game on a simple graph consists of moves that remove two pebbles from a vertex of the graph and add one pebble to an adjacent vertex. We consider an impartial two-player pebbling game, where the winner of the game is the last player to make an allowable pebbling move. In this paper, we characterize the winning positions when this game is played on a complete graph Kn with at least n + 2 pebbles if n ≥ 5 is odd and at least n + 7 pebbles if n ≥ 6 is even. This characterization is independent of how the pebbles are initially distributed on the vertices and depends only on the parity of the total number of pebbles used in the game.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A340631.)

Received March 25 2021; revised version received May 4 2021. Published in Journal of Integer Sequences, May 18 2021.

Return to Journal of Integer Sequences home page