Trail Trap on Cubic Hamiltonian Graphs (Spring 2025)


Trail Trap is a game on graphs where two players compete to form a long trail as follows. One player starts by choosing any edge and moving a token from one endpoint to the other; the other player then chooses a different edge and does the same. Alternating turns, each player moves their token along an unused edge from its current vertex to an adjacent vertex, until one player cannot move and loses. The primary question to ask is: given a particular graph or class of graphs, which player wins? 


For arbitrary graphs, this question is very challenging, but for restricted graph classes, such as trees, the problem becomes more tractable. In this project, we will investigate the winning player for the class of cubic Hamiltonian graphs. I.e. Graphs where every vertex has degree 3 and there is a single cycle which covers all vertices. This seems to be one of the simplest classes of graphs which cannot be handled via current techniques. 

For more information contact Nicholas Sieger (nsieger@iastate.edu)

People:

Pre-requisites: