Bounds on the 2-rainbow domination number of graphs

DOI10.1007/S00373-012-1158-YMaRDI QIDQ354420zbMATH OpenOpenAlexFDO

Authors Nader Jafari Rad, Y. Wu

Publication date 19 July 2013

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.0988

zbMATH Keywords

domination numberCartesian product2-rainbow domination number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Abstract: A {it 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 $vinV(G)$, $f(v)=emptyset$ implies $$. The {it 2-rainbow domination number $gamm{a}_{r2}(G)$} of a graph $G$ is the minimum $w(f)=Sigm{a}_{vinV}|f(v)|$ over all such functions $f$. Let $G$ be a connected graph of order $|V(G)|=ngeq3$. We prove that $gamm{a}_{r2}(G)leq3n/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 $gamm{a}_{r2}(G)$ in terms of diameter are also given.

Recommendations

• On 2-rainbow domination and roman domination in graphs
• Note on 2-rainbow domination and Roman domination in graphs
• New bounds on the rainbow domination subdivision number
• Independent 2-rainbow domination in graphs
• Bounding the rainbow domination number of a tree in terms of its annihilation number

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3284071 (Why is no real title available?)
• 2-rainbow domination in generalized petersen graphs \(P(n,3)\)
• 2-rainbow domination of generalized Petersen graphs \(P(n,2)\)
• Note on 2-rainbow domination and Roman domination in graphs
• On dominating the Cartesian product of a graph and K₂
• On the 2-rainbow domination in graphs
• Paired-domination of Cartesian products of graphs
• Rainbow domination in graphs
• Rainbow domination on trees

Cited in

(51)

• Rainbow domination in Cartesian product of paths and cycles
• On 2-rainbow domination number of functigraph and its complement
• Outer independent rainbow dominating functions in graphs
• scientific article; zbMATH DE number 7227817 (Why is no real title available?)
• On 2-rainbow domination and roman domination in graphs
• Bounding the \(k\)-rainbow total domination number
• The \(k\)-rainbow bondage number of a digraph
• General upper bounds on independent \(k\)-rainbow domination
• On the rainbow domination number of digraphs
• scientific article; zbMATH DE number 6107250 (Why is no real title available?)
• 2-rainbow domination number of \(C_n\square C_5\)
• Independent Roman \(\{2 \}\)-domination in graphs
• Independent 2-rainbow domination in graphs
• Rainbow domination in graphs
• Weak \(\{2\}\)-domination number of Cartesian products of cycles
• 2-rainbow domination number of Cartesian products: \(C_{n}\square C_{3}\) and \(C_{n}\square C_{5}\)
• New bounds on the rainbow domination subdivision number
• A sharp upper bound for the rainbow 2-connection number of a 2-connected graph
• A note on the 2-rainbow bondage numbers in graphs
• Bounding the rainbow domination number of a tree in terms of its annihilation number
• A sharp upper bound on the independent 2-rainbow domination in graphs with minimum degree at least two
• Rainbow domination numbers on graphs with given radius
• The \(k\)-rainbow bondage number of a graph
• On the sum of the total domination numbers of a digraph and its converse
• A note on total domination and 2-rainbow domination in graphs
• Total 2-rainbow domination numbers of trees
• The \(l\)-distance \(k\)-rainbow domination numbers of graphs
• Bounds on weak Roman and 2-rainbow domination numbers
• Further results on maximal rainbow domination number
• Algorithmic aspects of the independent 2-rainbow domination number and independent Roman \(\{2\}\)-domination number
• scientific article; zbMATH DE number 6929515 (Why is no real title available?)
• Total \(k\)-rainbow domination numbers in graphs
• Rainbow domination in the Cartesian product of directed paths
• On the outer independent 2-rainbow domination number of Cartesian products of paths and cycles
• Relating 2-rainbow domination to Roman domination
• Upper bound on 3-rainbow domination in graphs with minimum degree 2
• The \(k\)-rainbow reinforcement numbers in graphs
• General bounds on rainbow domination numbers
• Independent 2-rainbow domination in trees
• Rainbow edge domination numbers in graphs
• The Cartesian product of cycles with small 2-rainbow domination number
• Graphs with large total 2-rainbow domination number
• 2-rainbow domination stability of graphs
• Total 2-rainbow domination in graphs: complexity and algorithms
• On the complexity of reinforcement in graphs
• Averaging 2-rainbow domination and Roman domination
• Roman \(\{2 \}\)-domination
• On the rainbow restrained domination number.
• On the 2-rainbow bondage number of planar graphs.
• A new upper bound on the independent 2-rainbow domination number in trees
• Outer-independent total 2-rainbow dominating functions in graphs

This page was built for publication: Bounds on the 2-rainbow domination number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q354420)