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 11.04.2018, Revised 22.10.2018, Accepted 03.11.2018, doi: 10.7151/dmgt.2191 | |
Abstract: A 2-rainbow dominating function (2RDF) 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∈V(G) with f(v)=\emptyset the condition \bigcup_{u∈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 2RDF with the additional condition that the subgraph of G induced by {v∈V(G)| f(v)\not=\emptyset } has no isolated vertex. The total 2-rainbow domination number, γ_{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 γ _{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 | |
Links: |