Opuscula Math. 40, no. 5 (2020), 599-615
https://doi.org/10.7494/OpMath.2020.40.5.599

 
Opuscula Mathematica

Outer independent rainbow dominating functions in graphs

Zhila Mansouri
Doost Ali Mojdeh

Abstract. A 2-rainbow dominating function (2-rD function) of a graph \(G=(V,E)\) is a function \(f:V(G)\rightarrow\{\emptyset,\{1\},\{2\},\{1,2\}\}\) having the property that if \(f(x)=\emptyset\), then \(f(N(x))=\{1,2\}\). The 2-rainbow domination number \(\gamma_{r2}(G)\) is the minimum weight of \(\sum_{v\in V(G)}|f(v)|\) taken over all 2-rainbow dominating functions \(f\). An outer-independent 2-rainbow dominating function (OI2-rD function) of a graph \(G\) is a 2-rD function \(f\) for which the set of all \(v\in V(G)\) with \(f(v)=\emptyset\) is independent. The outer independent 2-rainbow domination number \(\gamma_{oir2}(G)\) is the minimum weight of an OI2-rD function of \(G\). In this paper, we study the OI2-rD number of graphs. We give the complexity of the problem OI2-rD of graphs and present lower and upper bounds on \(\gamma_{oir2}(G)\). Moreover, we characterize graphs with some small or large OI2-rD numbers and we also bound this parameter from above for trees in terms of the order, leaves and the number of support vertices and characterize all trees attaining the bound. Finally, we show that any ordered pair \((a,b)\) is realizable as the vertex cover number and OI2-rD numbers of some non-trivial tree if and only if \(a+1\leq b\leq 2a\).

Keywords: outer-independent rainbow domination, \(K_{1,r}\)-free graphs, trees.

Mathematics Subject Classification: 05C69.

Full text (pdf)

  • Communicated by Dalibor Fronček.
  • Received: 2019-12-15.
  • Revised: 2020-06-27.
  • Accepted: 2020-07-01.
  • Published online: 2020-10-10.
Opuscula Mathematica - cover

Cite this article as:
Zhila Mansouri, Doost Ali Mojdeh, Outer independent rainbow dominating functions in graphs, Opuscula Math. 40, no. 5 (2020), 599-615, https://doi.org/10.7494/OpMath.2020.40.5.599

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.