IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Game Total Domination and Total Dominating Sequences

  • April 1, 2016
  • 2:30 p.m.
  • LeConte 312

Abstract

Two players, Dominator and Staller, alternate choosing a vertex from a graph G that has no isolated vertices. Each vertex chosen by a player must totally dominate (i.e., must be adjacent to ) at least one vertex that was not totally dominated by the set of vertices chosen previously in the game. The game ends when no such vertex can be chosen. Both players use an optimal strategy--Dominator to end the game as quickly as possible and Staller to prolong the game. If Dominator is the first to choose a vertex, the number of vertices chosen is the game total domination number of G, denoted $\gamma _ {tg}(G)$. I will present some of the basic results about the game total domination number as well as some progress on proving the conjectured upper bound of 3n/4 on this invariant for a graph of order n.

If both players are attempting to make the game on G last as long as possible, the number of vertices chosen is called the Grundy total domination number of G. This is equivalent to the worst outcome from an online version of total domination in which vertices are processed one at a time and the only information available when a vertex is processed is its open neighborhood. I will present some results on lower and upper bounds for this graphical invariant for various classes of graphs.

This is joint work with various subsets of Boštjan Brešar, Mike Henning and Sandi Klavžar.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC