### 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)$.

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.