×

Bounds on the 2-rainbow domination number of graphs. (English) Zbl 1268.05154

Summary: A 2-rainbow domination function of a graph \(G\) is a function \(f\) that assigns to each vertex a set of colors chosen from the set \(\{1,2\}\), such that for any \(v\in V(G)\), \(f(v)=\emptyset\) implies \(\bigcup_{u\in N(v)}f(u)=\{1,2\}\). The 2-rainbow domination number \(\gamma_{r2}(G)\) of a graph \(G\) is the minimum \(w(f)=\Sigma_{v\in V}| f(v)|\) over all such functions \(f\). Let \(G\) be a connected graph of order \(| V(G)|=n\geq 3\). We prove that \(\gamma_{r2}(G)\leq 3n/4\) and we characterize the graphs achieving equality. We also prove a lower bound for 2-rainbow domination number of a tree using its domination number. Some other lower and upper bounds of \(\gamma_{r2}(G)\) in terms of diameter are also given.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bollobás B.: Modern Graph Theory, 2nd edn. Springer, New York (1998) · Zbl 0902.05016 · doi:10.1007/978-1-4612-0619-4
[2] Brešar B., Henning M.A., Rall D.F.: Paired-domination of Cartesian products of graphs. Util. Math. 73, 255-265 (2007) · Zbl 1161.05053
[3] Brešar B., Henning M.A., Rall D.F.: Rainbow domination in graphs. Taiwanese J. Math. 12, 201-213 (2008) · Zbl 1163.05046
[4] Brešar B., Kraner Šumenjak T.: On the 2-rainbow domination in graphs. Discrete Appl. Math. 155, 2394-2400 (2007) · Zbl 1126.05091 · doi:10.1016/j.dam.2007.07.018
[5] Chang G.J., Wu J., Zhu X.: Rainbow domination on trees. Discrete Appl. Math. 158, 8-12 (2010) · Zbl 1226.05191 · doi:10.1016/j.dam.2009.08.010
[6] Hartnell B.L., Rall D.F.: On dominating the Cartesian product of a graph and K2. Discuss. Math. Graph Theory 24, 389-402 (2004) · Zbl 1063.05107 · doi:10.7151/dmgt.1238
[7] Haynes T.W., Hedetniemi S.T., Slater P.J.: Fundamentals of Domination in Graphs. Marcel Dekker Inc., New York (1998) · Zbl 0890.05002
[8] Tong C., Lin X., Yang Y., Luo M.: 2-Rainbow domination of generalized Petersen graphs P(n,2). Discrete Appl. Math. 157, 1932-1937 (2009) · Zbl 1183.05061 · doi:10.1016/j.dam.2009.01.020
[9] Vizing V.G.: Some unsolved problems in graph theory. Uspekhi Mat. Nauk 23, 117-134 (1968) · Zbl 0177.52301
[10] Wu Y., Xing H.: Note on 2-rainbow domination and Roman domination in graphs. Appl. Math. Lett. 23, 706-709 (2010) · Zbl 1213.05199 · doi:10.1016/j.aml.2010.02.012
[11] Xu G.: 2-Rainbow domination in generalized Petersen graphs P(n,3). Discrete Appl. Math. 157, 2570-2573 (2009) · Zbl 1209.05175 · doi:10.1016/j.dam.2009.03.016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.