Foolproof eternal domination in the all-guards move model (Q2905572)

In the \(m\)-eternal vertex protection problem, guards are placed at vertices of a graph \(G\) and must protect \(G\) against an infinite sequence of attacks. The guards must occupy a dominating set of \(G\) at all times. When a vertex \(v\) is attacked, all guards can move to adjacent vertices; however, the attacked vertex may choose a neighboring guard, and require that specific guard to move to \(v\). The minimum number of guards needed to protect against any possible sequence of attacks is called the \(m\)-eternal domination number of \(G\), denoted \(\rho _m^{\infty }(G)\).NEWLINENEWLINEIn this paper, the authors introduce the parameter \(\rho _m^{\infty }\). They establish several bounds on \(\rho _m^{\infty }(G)\) in terms of related graph parameters, such as the domination number \(\gamma (G)\), the \(m\)-eternal domination number \(\gamma _m^{\infty }(G)\), and the \(m\)-eternal vertex protection number \(\alpha _m^{\infty }(G)\). Among these bounds are the following: NEWLINE{\parindent=6mmNEWLINE\begin{itemize}\item[--]always \(\rho _{m}^{\infty }(G) \leq 2 {\gamma (G) \choose 2} + 2\gamma (G)\); NEWLINE\item[--]always \(\gamma _m^{\infty }(G) \leq \rho _m^{\infty }(G) \leq \alpha _m^{\infty }(G)\); NEWLINE\item[--]when \(G\) is connected and bipartite, \(\rho _m^{\infty }(G) \leq \beta (G)\) \newline(where \(\beta (G)\) denotes the independence number of \(G\)); NEWLINE\item[--]always \(\rho _m^{\infty }(G) \leq 2\theta (G)\) \newline(where \(\theta (G)\) denotes the clique cover number of \(G\)); NEWLINE\item[--]when \(T\) is a tree, \(\rho _m^{\infty }(T) = \gamma _m^{\infty }(T)\). NEWLINENEWLINE\end{itemize}} NEWLINEThe authors also show that \(\rho _{m}^{\infty }(G) \in \bigl \{\gamma (G),\gamma (G)+1\bigr \}\) for all connected split graphs \(G\), and characterize those graphs attaining each value.