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 $V-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 ${\gamma }_{t,coi}(G)$. In this work we study some complexity and combinatorial properties of ${\gamma }_{t,coi}(G)$. Specifically, we prove that deciding whether ${\gamma }_{t,coi}(G)\le k$ for a given integer $k$ is an NP-complete problem and give several bounds on ${\gamma }_{t,coi}(G)$. Also, since any total co-independent dominating set is also a total dominating set, we characterize all the trees having equal total co-independent domination number and total domination number.

22 pages