The possible cardinalities of global secure sets in cographs (Q764303): Difference between revisions

A global secure set of a graph \(G\) is a subset of vertices \(SD\subseteq V(G)\) such that: {\parindent=8mm \begin{itemize}\item[(i)]\(SD\) is a dominating set; \item[(ii)]\(|N[X]\cap SD|\geq |N[X]-SD|\) holds for every subset \(X\subseteq SD\), where \(N[X]\) is the closed neighborhood of \(X\subseteq V(G)\). \end{itemize}} The minimum cardinality of a global secure set in the graph \(G\) is denoted by \(\gamma _{s}(G)\). The graph \(G\) is said to be \(\gamma _{s}\)-monotone if, for every \(k\in \{\gamma _{s}(G),\gamma _{s}(G)+1,\ldots ,n\}\), it has a global secure set of cardinality \(k\). In this paper some results concerning the minimum cardinality of global secure sets in the class of cographs are presented, where cographs are graphs without induced path on four vertices. It is shown that not every connected cograph is \(\gamma _{s}\)-monotone and the best possible upper bound on the minimum cardinality of global secure sets in this class of graphs is given. A linear-time algorithm which can find a global secure set of any proper cardinality in a special subclass of cographs is presented. This subclass of cographs, containing trivially perfect graphs, such that every graph which belongs to it is \(\gamma _{s}\)-monotone is described in the paper by a recursive definition.