DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

H.A. Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, L. Shahbazi, S.M. Sheikholeslami

Title:

Total 2-rainbow domination numbers in trees

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-04-11, Revised: 2018-10-22, Accepted: 2018-11-03, https://doi.org/10.7151/dmgt.2191

Abstract:

A $2$-rainbow dominating function ($2$RDF) of a graph $G=(V(G),E(G))$ is a function $f$ from the vertex set $V(G)$ to the set of all subsets of the set $\{1,2\}$ such that for every vertex $v\in V(G)$ with $f(v)=\emptyset $ the condition $\bigcup_{u\in N(v)}f(u)=\{1,2\}$ is fulfilled, where $N(v)$ is the open neighborhood of $v$. A total $2$-rainbow dominating function $f$ of a graph with no isolated vertices is a $2$RDF with the additional condition that the subgraph of $G$ induced by $\{v\in V(G)| f(v)\not=\emptyset \}$ has no isolated vertex. The total $2$-rainbow domination number, $\gamma_{tr2}(G)$, is the minimum weight of a total $2$-rainbow dominating function of $G$. In this paper, we establish some sharp upper and lower bounds on the total $2$-rainbow domination number of a tree. Moreover, we show that the decision problem associated with $\gamma _{tr2}(G)$ is NP-complete for bipartite and chordal graphs.

Keywords:

$2$-rainbow dominating function, $2$-rainbow domination number, total $2$-rainbow dominating function, total $2$-rainbow domination number

PDF
Close