Mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on either its vertices or its edges. A defense against vertex attacks naturally corresponds to maintaining a dominating set, and a defense against edge attacks corresponds to maintaining a vertex cover. These games were introduced by Klostermeyer and Mynhardt.
To be explicit, we are considering two player games --- between players whom we will refer to as the attacker and defender --- on a simple, undirected graph G. In the beginning, the defender can choose to place guards on some of the vertices of G. The attacker's move involves choosing an edge (vertex) to attack. The defender is able to defend this attack if she can move the guards along the edges of the graph in such a way that at least one guard moves along the attacked edge (vertex). If such a movement is not possible, then the attacker wins. If the defender can defend the graph against an infinite sequence of attacks, then the defender wins. The minimum number of guards with which the defender has a winning strategy is called the eternal vertex cover (eternal domination) number of the graph G.
We will explore some structural aspects of these parameters, with a special focus on relating them to the corresponding static parameters. In particular, we will consider when the eternal vertex cover number coincides with the minimum vertex cover, and explore a structural characterization on bipartite graphs (based on joint work with Saraswati Nanoti). We will also explore the question of eternal domination on infinite grids (based on joint work with Tiziana Calamoneri, Federico Corò, Saraswati Girish Nanoti and Giacomo Paesani).
Short Bio:
Neeldhara Misra is a Smt. Amba and Sri. V S Sastry Chair Associate Professor of Computer Science and Engineering at the Indian Institute of Technology, Gandhinagar. She completed her PhD from the Institute for Mathematical Sciences in 2012 in Theoretical Computer Science, followed by a post-doc at the Department of Computer Science and Automation at IISc. Her research interests include the design and analysis of algorithms for graph optimization problems and computational social choice. She is also interested in visualizations and other methods to communicate computational thinking at an elementary level.
