Search
Close this search box.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

Dynamic Dominating Sets: the Eviction Model for Eternal Domination

William F. Klostermeyer Mary Lawrence1, Gary MacGillivray2
1School of Computing School of Computing University of North Florida University of North Florida Jacksonville, FL 32224-2669 Jacksonville, FL 32224-2669
2Dept. of Mathematics and Statistics University of Victoria Victoria, Canada
  • Published: 31/05/2016

Abstract

We consider a discrete-time dynamic problem in graphs in which the goal is to maintain a dominating set over an infinite sequence of time steps. At each time step, a specified vertex in the current dominating set must be replaced by a neighbor. In one version of the problem, the only change to the current dominating set is replacement of the specified vertex. In another version of the problem, other vertices in the dominating set can also be replaced by neighbors. A variety of results are presented relating these new parameters to the eternal domination number, domination number, and independence number of a graph.

Keywords: dominating set, eternal dominating set, connected dominat- ing set, independent set, neo-colonization
Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin
1970-2024 CP (Manitoba, Canada) unless otherwise stated.
Citation
William F. Klostermeyer Mary Lawrence, Gary MacGillivray. Dynamic Dominating Sets: the Eviction Model for Eternal Domination[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 097. 247-269. DOI: .