×

Eternally secure sets, independence sets and cliques. (English) Zbl 1102.05043

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\).
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\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 1067.05051
PDFBibTeX XMLCite