Trees with equal total domination and 2-rainbow domination numbers


Zehui Shao, Seyed Mahmoud Sheikholeslami, Bo Wang, Pu Wu, Xiaosong Zhang




A 2-rainbow dominating function (2RDF) of a graph G is a function f : V(G) → P({1, 2}) such that for each v ∈ V(G) with f (v) = ∅we have⋃u∈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 ) = ∑ v∈V(G) | f (v)|. The minimum weight over all 2RDFs of G is called the 2-rainbow domination number of G, which is denoted by γr2(G). A subset S of vertices of a graph G without isolated vertices, is a total dominating set of G if every vertex in V(G) has a neighbor in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. Chellali, Haynes and Hedetniemi conjectured that γt(G) ≤ γr2(G) [M. Chellali, T.W. Haynes and S.T. Hedetniemi, Bounds on weak Roman and 2-rainbow domination numbers, Discrete Appl. Math. 178 (2014), 27–32.], and later Furuya confirmed the conjecture [M. Furuya, A note on total domination and 2-rainbow domination in graphs, Discrete Appl. Math. 184 (2015), 229–230.]. In this paper, we provide a constructive characterization of trees T with γr2(T) = γt(T).