On the Hamiltonicity of the k-Regular Graph Game
Indexed on: 04 Oct '18Published on: 03 Oct '18Published in: Graphs and Combinatorics
Abstract
We consider a game played on an initially empty graph where two players alternate drawing an edge between vertices subject to the condition that no degree can exceed k. We show that for \(k=3\), either player can avoid a Hamilton cycle, and for \(k\ge 4\), either player can force the resulting graph to be Hamiltonian.
