Independent Transversal Dominating Sets in Graphs: Complexity and Structural Properties


Hossein Abdollahzadeh Ahangar, Vladimir Samodivkin, Ismael G. Yero




A dominating set of a graph G which intersects every independent set of maximum cardinality in $G$ is called an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of $G$ and is denoted by $\gamma_{it}(G)$. In this paper we study some complexity issues on some independent transversal domination related problems. On the other side, we prove that for every integers $a,b,c$ with $a\leq b\leq(a+c)$, there exists a graph $G$ such that $G$ has domination number a, minimum degree $c$ and independent transversal domination number $b$. We also give some other properties of independent transversal dominating sets in graphs.