Eternally secure sets, independence sets and cliques (Q2369386): Difference between revisions

For a numbering \(R\) of the vertices of a graph \(G= (V, E)\), \(R(i)\) denotes the \(i\)th vertex in \(R\). A set \(D\subseteq V\) is an eternal secure set if, for all possible sequences \(R\), there exists a sequence \(D_0, D_1, \ldots\) such that \(D_i = (D_{i-1}\setminus\{v\})\cup \{R(i)\}\), \(R(i)\in N(v)\cup\{v\}\), and each \(D_i\) is a dominating set. The eternal security number \(\gamma_\infty(G)\) is the size of a smallest eternal secure set in \(G\). \textit{W. Goddard} et al. [J. Comb. Math. Comb. Comput. 52, 169--180 (2005; Zbl 1067.05051)] conjectured that if \(\gamma_\infty(G) = \beta(G)\) then \(\beta(G) = \theta(G)\), where \(\beta(G)\) is the independence number and \(\theta(G)\) is the clique-covering number of \(G\). The present authors prove this conjecture in case \(\beta(G)=2\) and give counterexamples in case \(\beta(G)\geq 3\).