Trees with Equal Total Domination and 2-Rainbow Domination Numbers

Abstract

A $2$-{\em rainbow dominating function} (2RDF) of a graph $G$ is a function $f : V (G) \rightarrow \mathcal{P}(\{1,2\})$
such that for each $v \in V(G)$ with $f(v) = \emptyset$ we have
$\bigcup_{u \in N(v)}f(u) = \{1, 2\}$.
For a 2RDF $f$ of a graph $G$, the weight $w(f)$ of
$f$ is defined as $w(f) = \sum_{v \in V(G)}|f(v)|$.
The minimum weight over all 2RDFs of $G$ is
called the $2$-{\em rainbow domination number} of $G$, which is denoted by
$\gamma_{r2}(G)$.
A subset $S$ of vertices of a graph $G$ without isolated vertex, is a
\emph{total dominating set} of $G$ if every vertex in $V(G)$ has a
neighbor in $S$. The \emph{ total domination number} $\gamma_t(G)$ is the
minimum cardinality of a total dominating set of $G$. Chellali, Haynes and Hedetniemi conjectured that $\gamma_t (G) \leq \gamma_{r2}(G)$ [M. Chellali, T. W. Haynesb, S. T. Hedetniemi,
Bounds on weak Roman and 2-rainbow domination numbers, Discrete Applied Mathematics 178 (2014) 27--32.], and later Furuya confirmed the conjecture.
In this paper,
we provide a constructive characterization of trees $T$ with $\gamma_{r2}(T)=\gamma_t(T)$.