Greedy approaches for Gold Grabbing on subclasses of split graphs
TL;DR
It is proved that for complete split graphs $CS_{(2,n)}$, the greedy strategy yields a sequence of moves that maximizes the game value, contributing to a better understanding of the structural conditions that ensure the optimality of simple strategies in graph-based combinatorial games.
Abstract
The Gold Grabbing Game is a combinatorial game on vertex-weighted graphs in which two players alternately remove vertices while maintaining graph connectivity, aiming to maximize the total collected weight. Although the literature has primarily focused on strategies that guarantee victory, the question of optimality --- i.e., maximizing total gain --- remains less explored. In this work, we investigate the behavior of the greedy strategy in this setting. We show that this approach is not optimal for general split graphs, highlighting structural limitations of this class. On the other hand, we prove that for complete split graphs $CS_{(2,n)}$, the greedy strategy yields a sequence of moves that maximizes the game value. As a consequence, the first player does not lose when the number of vertices is even. These results contribute to a better understanding of the structural conditions that ensure the optimality of simple strategies in graph-based combinatorial games.