Eternal Total Domination in Graphs

William F.Klostermeyer1, C.M. Mynhardt2
1School of Computing University of North Florida Jacksonville, FL 32224-2669
2Department of Mathematics and Statistics University of Victoria, P.O. Box 3060 STN CSC Victoria, BC, CANADA V8W 3R4

Abstract

Eternal domination of a graph requires the vertices of the graph to be protected, against infinitely long sequences of attacks, by guards located at vertices, with the requirement that the configuration of guards induces a dominating set at all times. We study some variations of this concept in which the configuration of guards induce total dominating sets. We consider two models of the problem: one in which only one guard moves at a time and one in which all guards may move simultaneously. A number of upper and lower bounds are given for the number of guards required.