We consider a dynamic domination problem for graphs in which an infinite sequence of attacks occur at vertices with guards and the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack and the resulting guard movements, the vertices containing guards form a dominating set of the graph. The minimum number of guards that can successfully defend the graph against such an arbitrary sequence of attacks is the m-eviction number. This parameter lies between the domination and independence numbers of the graph. We characterize the classes of trees for which the m-eviction number equals the domination number and the independence number, respectively.
M. Anderson, C. Barrientos, R. Brigham, J. Carrington, R. Vitray and J. Yellen (2007). Maximum demand graphs for eternal security. J. Combin. Math. Combin. Comput.. 61, 111-128 A. P. Burger, E. J. Cockayne, W. R. Grundlingh, C. M. Mynhardt, J. H. van Vuuren and W. Winterbach (2004). Infinite order domination in graphs. J. Combin. Math. Combin. Comput.. 50, 179-194 E. J. Cockayne, O. Favaron, C. M. Mynhardt and J. Puech (2000). A characterisation of $(\gamma,i)$-trees. J. Graph Theory. 34, 277-292 M. Dorfling, W. Goddard, M A. Henning and C. M. Mynhardt (2006). Construction of trees and graphs with equal domination parameters. Discrete Math.. 306, 2647-2654 W. Goddard, S. M. Hedetniemi and S. T. Hedetniemi (2005). Eternal security in graphs. J. Combin. Math. Combin. Comput.. 52, 169-180 J. Goldwasser and W. F. Klostermeyer (2008). Tight bounds for eternal dominating sets in graphs. Discrete Math.. 308, 2589-2593 J. L. Goldwasser, W. F. Klostermeyer and C. M. Mynhardt (2013). Eternal protection in grid graphs. Util. Math.. 91, 47-64 W. F. Klostermeyer, M. Lawrence and G. MacGillivray An eternal domination problem related to file migration. to appear in J. Combin. Math. Combin. Comput.. W. F. Klostermeyer and G. MacGillivray (2007). Eternal security in graphs of fixed independence number. J. Combin. Math. Combin. Comput.. 63, 97-101 W. F. Klostermeyer and G. MacGillivray (2009). Eternal dominating sets in
graphs. J. Combin. Math. Combin. Comput.. 68, 97-111 W. F. Klostermeyer and C. M. Mynhardt (2009). Edge protection in graphs. Australas. J. Combin.. 45, 235-250 W. F. Klostermeyer and C. M. Mynhardt (2011). Graphs with equal eternal vertex cover and eternal domination numbers. Discrete Math.. 311, 1371-1379 W. F. Klostermeyer and C. M. Mynhardt (2012). Vertex covers and eternal dominating sets. Discrete Appl. Math.. 160, 1183-1190 W. F. Klostermeyer and C. M. Mynhardt (2012). Eternal total domination in graphs. Ars Combin. 107, 473-492 C. M. Mynhardt (1999). Vertices contained in every minimum dominating set of a tree. J. Graph Theory. 31, 163-177
Klostermeyer, W. and Mynhardt, C. (2015). A dynamic domination problem in trees. Transactions on Combinatorics, 4(4), 15-31. doi: 10.22108/toc.2015.7590
MLA
Klostermeyer, W. , and Mynhardt, C. . "A dynamic domination problem in trees", Transactions on Combinatorics, 4, 4, 2015, 15-31. doi: 10.22108/toc.2015.7590
HARVARD
Klostermeyer, W., Mynhardt, C. (2015). 'A dynamic domination problem in trees', Transactions on Combinatorics, 4(4), pp. 15-31. doi: 10.22108/toc.2015.7590
CHICAGO
W. Klostermeyer and C. Mynhardt, "A dynamic domination problem in trees," Transactions on Combinatorics, 4 4 (2015): 15-31, doi: 10.22108/toc.2015.7590
VANCOUVER
Klostermeyer, W., Mynhardt, C. A dynamic domination problem in trees. Transactions on Combinatorics, 2015; 4(4): 15-31. doi: 10.22108/toc.2015.7590
)
