Eternal total domination in graphs. (Q2864475)

The graphs considered are finite and simple. A vertex set \(D\) in the graph \(G=(V,E)\) is called a dominating set if every vertex in \(V-D\) is adjacent to some vertex in \(D.\) If, in addition, the subgraph induced by \(D\) has no isolated vertices, then one calls \(D\) a total dominating set. Note that a total dominating set exists iff \(G\) has no isolated vertices. The domination number \(\gamma (G)\) is the size of a smallest dominating set. The total dominating number \(\gamma _t(G)\) is defined analogously. An eternal dominating set (EDS) of \(G\) is a dominating set \(D\) such that for every sequence of vertices \(R=r_1,r_2,\dots \) there is a sequence of dominating sets \(D_1,D_2,\dots \) where \(D=D_1\) and a sequence of vertices \(s_1,s_2,\dots \) where \(s_i\in D_i\cap N[r_i]\) such that \(D_{i+1}:=(D_i-\{s_i\})\cup \{r_i\}\), and where \(N[r_i]\) denotes the closed neighborhood of \(r_i.\) One also says that \(D_{i+1}\) is obtained from \(D_{i}\) by moving \(s_i\) to its neighbor \(r_i.\) Likewise, the eternal dominating number \(\gamma ^{\infty }(G)\) is the minimum cardinality amongst all EDSs. An eternal total dominating set (ETDS) is defined similarly as an EDS except that the above sets \(D_{i}\) are total dominating sets; the corresponding eternal total domination number \(\gamma _t^{\infty }(G)\) is defined analogously. Moreover, one can generalize an ETDS by allowing in the transition from \(D_{i}\) to \(D_{i+1}\) to move several vertices of \(D_{i}\) to neighbouring vertices, and call this generalization an \(m\)-ETDS; the corresponding parameter is denoted by \(\gamma _{mt}^{\infty }(G).\) The authors introduce additional parameters. They also relate this latter parameter to the clique covering number \(\theta (G)\) by showing the following:NEWLINENEWLINETheorem 8: If \(G\) is connected and \(\theta (G)\geq 2\) , then \(\gamma _{mt}^{\infty }(G)\leq 2\theta (G)-1.\) This bound is sharp for all \(\theta (G)\geq 2.\) They go on to establish necessary and sufficient conditions when this upper bound is achieved (Theorem 9). They also prove:NEWLINENEWLINETheorem 10: For all graphs \(G=(V,E)\) without isolated vertices, \(\gamma _t^{\infty }(G)>\gamma ^{\infty }(G).\)NEWLINENEWLINEIt is noted that this inequality is best possible in that, e.g., the graphs \(G=K_{1,m}\) satisfy \(\gamma _t^{\infty }(G)=\gamma ^{\infty }(G)+1.\) They also prove the following inequalities for graphs without isolated vertices: \(\gamma _t^{\infty }(G)\leq 2\gamma ^{\infty }(G)\leq 2\theta (G)\) (see Theorem 11), \(\gamma _{mt}^{\infty }(G)\leq 2\gamma (G)\) (see Theorem 12). Finally, they establish equations for the parameters \(\gamma _{t}^{\infty }(G)\), \(\gamma _{mt}^{\infty }(G)\), resp., where \(G\) is a path or tree (Theorems 13 and 14).