Eternally secure sets, independence sets and cliques
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\).
- Eternal domination on prisms of graphs
- Domination, eternal domination, and clique covering
- scientific article; zbMATH DE number 5968475 (Why is no real title available?)
- Trees with large \(m\)-eternal domination number
- Eternal and Secure Domination in Graphs
- The guarding game is E-complete
- Independent protection in graphs
- Eternal security in graphs of fixed independence number
- Complexity of eternal security
- A note on the paper ``Eternal security in graphs by Goddard, Hedetniemi, and Hedetniemi (2005)
- Guard games on graphs: keep the intruder out!
This page was built for publication: Eternally secure sets, independence sets and cliques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369386)
