A total dominating set $S\subset V(G)$ is a set of vertices such that $\forall v\in V(G)$, $v$ has a neighbour in $S$. The minimum total dominating set of $G$ is a total dominating set of $G$ of minimum possible size. The minimum total domination number of $G$ is represented by $\gamma_t(G)$.It is known that MTDS is $NP-complete$ for general graphs, bipartite graphs, chordal graphs, etc. [REFERENCE: Henning, Michael A.. “A survey of selected recent results on total domination in graphs.” Discret. Math. 309 (2009): 32-63.]

Do we know anything about hardness of MTDS on triangle-free graphs of bounded degree?Or triangle-free graphs in general? ( A graph is triangle-free if any three vertices does not form a triangle).

  • 2
    $\begingroup$ All bipartites are triangle free. That answers your second question. $\endgroup$ Jul 3, 2023 at 9:23
  • $\begingroup$ Yes that's correct. $\endgroup$ Jul 3, 2023 at 9:32
  • $\begingroup$ It would be good if you could tell the motivation for studying this version since there could be many such variants. $\endgroup$ Jul 3, 2023 at 10:05
  • $\begingroup$ So I am studying this specific kind of proper coloring of graphs called "cd-coloring" in which every color class is dominated by atleast one vertex. The cd-chromatic number is denoted by $\chi_{cd}$. So it is proven that for triangle -free graphs $G$ ,$\chi_{cd}(G)=\gamma_t(G)$. Right now my motive is to study cd-colorability in regular graphs(in particular cubic graphs). I want to prove this is $NP-hard$ for triangle-free cubic graphs. So I tried to reduce *total domination in cubic graphs*(which is $NP-complete$) to cd -colorability in cubic graphs, but till now am not successful. $\endgroup$ Jul 3, 2023 at 13:22
  • $\begingroup$ (Continuing) So I am searching for total-domination $NP-completeness$ results for triangle-free graphs of bounded degree, So that I can reduce it to cd-colorability of some triangle-free $k$-regular graphs, thereby proving it $NP-complete$. $\endgroup$ Jul 3, 2023 at 13:25

1 Answer 1


The problem is indeed $\mathsf{NP}$-hard on bipartite graphs (which are triangle-tree) of degree at most $3$. See Theorem 6 of this paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.