Independent transversal dominating sets in graphs: complexity and structural properties

Hossein Abdollahzadeh Ahangar, Vladimir Samodivkin, Ismael G. Yero


Let $G$ be a graph. A dominating set of $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\le b\le 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.

Full Text:



  • There are currently no refbacks.