A Fine-Grained Complexity of Co-Secure Domination for Some Subclasses of Chordal Graphs

For a connected graph $G=(V,E)$, a set $D\subseteq V$ is a co-secure dominating set if $D$ is a dominating set of $G$ and for each vertex $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 of $G$. In this article, we present bounds on the co-secure domination number (size of minimum co-secure dominating set) in some restricted 2-trees, a popular subclass of chordal graphs. We also show an interesting dichotomy that the co-secure dominating set problem is NP-complete on $K_{1,r}$-free split graphs, $r\ge 4$, whereas it is linear-time solvable on $K_{1,3}$-free split graphs.