On Computational and Combinatorial Properties of the Total Co-independent Domination Number of Graphs

Abstract

A subset D of vertices of a graph G is a total dominating set if every vertex of G is adjacent to at least one vertex of D. The total dominating set D is called a total co-independent dominating set if the subgraph induced by $\mathit{V}\mathbf{-}\mathit{D}$ is edgeless and has at least one vertex. The minimum cardinality of any total co-independent dominating set is the total co-independent domination number of G and is denoted by ${\mathit{\gamma }}_{\mathit{t},\mathbf{c}\mathbf{o}\mathbf{i}}\mathbf{(}\mathit{G}\mathbf{)}$⁠. In this work we study some complexity and combinatorial properties of ${\mathit{\gamma }}_{\mathit{t},\mathbf{c}\mathbf{o}\mathbf{i}}\mathbf{(}\mathit{G}\mathbf{)}$⁠. Specifically, we prove that deciding whether ${\mathit{\gamma }}_{\mathit{t},\mathbf{c}\mathbf{o}\mathbf{i}}\mathbf{(}\mathit{G}\mathbf{)}\mathbf{\le }\mathit{k}$ for a given integer k is an NP-complete problem and give several bounds on ${\mathit{\gamma }}_{\mathit{t},\mathbf{c}\mathbf{o}\mathbf{i}}\mathbf{(}\mathit{G}\mathbf{)}$⁠. Moreover, since any total co-independent dominating set is a total dominating set, we characterize all the trees having equal total co-independent domination number and total domination number.