Dynamic dominating sets: the eviction model for eternal domination (Q2829356)

In a graph \(G = (V,E)\), a dominating set \(D\) is a subset of the vertices \(V\) such that every vertex is either in \(D\) or adjacent to one. Applications of dominating sets include communications, distributed computing and security. For instance, each node in the graph represents a strategic site that needs protection, and two nodes are connected by an edge if one site can be guarded from the other. If one puts a guard at each site, then all sites are guarded.NEWLINENEWLINEA dynamic dominating set is a dynamical system of dominating sets obtained through a two-player games between a defender and an attacker. At step \(i\), the attacker removes node \(r_i \in D_i\), and the defender must produce a new dominating set \(D_{i+1}\). Depending on the variation, there are different constraints on how \(D_{i+1}\) may be obtained from \(D_i\) and \(r_i\). This paper considers two variants of this game. In the ``one-guard move'' variant, \(D_{i+1}\) is obtained from \(D_i\) by adding in a neighbor of \(r_i\) to \(D_i - r_i\). In the ``all-guard move'' variant, in addition, any other nodes \(v \in D_{i+1}\) can be exchanged for one of its neighbor, as long as this neighbor is not \(r_i\). The defender wins if they can always produce \(D_{i+1}\), else, the attacker wins. An eternal dominating set \(D\) is one such that if \(D_1 = D\), then the defender wins regardless of the attacker moves. The eternal domination number is the size of the smallest eternal dominating set. This invariant is denoted \(e^\infty(G)\) for the ``one-guard move'' and \(e^\infty m(G)\) for the ``all-guard move'' model. Problems in this area include find the eternal domination number, and relate it to various other invariants of the graph. In this particular paper, the authors showed that for a large class of graphs, \(e^\infty(G) \geq \beta(G) \geq e^\infty m(G)\), where \(\beta(G)\) is the independence number of \(G\). They further showed that this bound is tight for certain families of graphs.