Bounds on the 2-rainbow domination number of graphs

DOI10.1007/S00373-012-1158-YzbMATH Open1268.05154arXiv1005.0988OpenAlexW2154705857MaRDI QIDQ354420FDOQ354420

Authors: Nader Jafari Rad, Y. Wu 

Publication date: 19 July 2013

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the 2-rainbow domination in graphs
• Rainbow domination in graphs
• Note on 2-rainbow domination and Roman domination in graphs
• Title not available (Why is that?)
• Rainbow domination on trees
• 2-rainbow domination of generalized Petersen graphs \(P(n,2)\)
• 2-rainbow domination in generalized petersen graphs \(P(n,3)\)
• On dominating the Cartesian product of a graph and K₂
• Paired-domination of Cartesian products of graphs

Cited In (51)

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