Session I.3 - Graph Theory and Combinatorics
Monday, June 12, 18:00 ~ 18:30
The total domination game
Leo Versteegen
University of Cambridge, UK - This email address is being protected from spambots. You need JavaScript enabled to view it.
The total domination game is a game played on a graph $G$ by 2 players, Dominator and Staller, who alternate in selecting vertices until each vertex in the graph $G$ has a neighbor in the set of selected vertices. Dominator's aim is to arrive at this state in as few moves as possible, while Staller wants to achieve the opposite. Henning, Klavžar, and Rall conjectured that if $G$ has $n$ vertices, then Dominator has a strategy to finish the game on $G$ within at most $3n/4$ moves. In this talk, I will sketch a proof of this conjecture, highlighting its use of linear programming.
Joint work with Julien Portier (University of Cambridge).