The co-secure domination in proper interval graphs (Q2078841)

Let \(G=(V,E)\) be a simple graph. A dominating set of \(G\) is a subset \(D\subseteq V\) such that every vertex not in \(D\) is adjacent to at least one vertex in \(D\). The cardinality of the smallest dominating set of \(G\), denoted by \(\gamma(G)\), is the domination number of \(G\). One kind of dominating set is co-secure dominating (CSD) that is defined as follows: A set \(D\subseteq V\) is a co-secure dominating set of \(G\) if \(D\) is a dominating set, and for each \(u\in D\) there exists a vertex \(v\in V\setminus D\) such that \(uv \in E\) and \((D\setminus \{u\})\cup \{v\}\) is a dominating set. The minimum cardinality of a co-secure dominating set in \(G\) is the co-secure domination number of \(G\). A graph \(G\) is an interval graph if \(V = \{1, 2, ...,n\}\) and there is an interval representation \({\mathcal I}(G)\) such that each vertex \(i\in V\) corresponds to an interval \(I_i\) in \({\mathcal I}(G)\) and \((i, j)\in E\) if and only if \(I_i\) and \(I_j\) intersect in the interval representation. The authors of this paper propose a linear-time algorithm for solving the CSD-problem in a proper interval graphs. They also propose a linear-time algorithm for finding the co-secure dominating set of proper interval graphs.