On the Hamiltonicity of the k-Regular Graph Game

Research paper by Jeremy Meza, Samuel Simon

Indexed on: 04 Oct '18Published on: 03 Oct '18Published in: Graphs and Combinatorics


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.