A dynamic domination problem in trees

Document Type : Research Paper

Authors

1 School of Computing University of North Florida

2 Department of Mathematics and Statistics University of Victoria

Abstract

‎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‎.


Keywords

Main Subjects

References

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
Transactions on Combinatorics
Volume 4, Issue 4 - Serial Number 4
December 2015
Pages 15-31

Files

History

  • Receive Date: 19 April 2014
  • Revise Date: 29 December 2014
  • Accept Date: 30 December 2014
  • Published Online: 01 December 2015

Share

How to cite

Statistics