Further results on outer independent 2-rainbow dominating functions of graphs
Open Access
- 27 July 2023
- journal article
- research article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 57 (4) , 1983-1993
Abstract
Let G = (V(G), E(G)) be a graph. A function f : V(G) → ℙ({1, 2}) is a 2-rainbow dominating function if for every vertex v with f(v) = ∅, f(N(v)) = {1, 2}. An outer-independent 2-rainbow dominating function (OI2RD function) of G is a 2-rainbow dominating function f for which the set of all v 2208 V(G) with f(v) = ∅ is independent. The outer independent 2-rainbow domination number (OI2RD number) γoir2(G) is the minimum weight of an OI2RD function of G. In this paper, we first prove that n/2 is a lower bound on the OI2RD number of a connected claw-free graph of order n and characterize all such graphs for which the equality holds, solving an open problem given in an earlier paper. In addition, a study of this parameter for some graph products is carried out. In particular, we give a closed (resp. an exact) formula for the OI2RD number of rooted (resp. corona) product graphs and prove upper bounds on this parameter for the Cartesian product and direct product of two graphs.
Keywords
All Related Versions
Funding Information
- The authors have not disclosed any funding. (Not applicable)
This publication has 10 references indexed in Scilit:
- A Note on Outer-Independent 2-Rainbow Domination in GraphsMathematics, 2022
- Topics in Domination in Graphs2020
- Outer independent rainbow dominating functions in graphsOpuscula Mathematica, 2020
- Outer-independent k-rainbow dominationJournal of Taibah University for Science, 2019
- Rainbow domination in the lexicographic product of graphsDiscrete Applied Mathematics, 2013
- Some results on Vizing’s conjecture and related problemsDiscrete Applied Mathematics, 2012
- Handbook of Product Graphs2011
- RAINBOW DOMINATION IN GRAPHSTaiwanese Journal of Mathematics, 2008
- A new graph product and its spectrumBulletin of the Australian Mathematical Society, 1978
- Computing the Characteristic polynomial of a graph1974