Generalized $k$-Rainbow and Generalized 2-Rainbow Domination in Graphs

Document Type : Research Article

Authors

1 Department of Mathematics and Computer Sciences, Faculty of Sciences University of Qom, Qom, Iran

2 Department of Mathematics, Farahan Branch, Islamic Azad University Farahan, Iran.

3 Department of Mathematics, Faculty of Sciences, University of Qom, Qom, Iran

Abstract

Assume we have a set of $k$ colors and to each vertex of a graph $G$ we assign an arbitray of these colors‎. ‎If we require that each vertex to set is assigned has in its closed neighborhood all $k$ colors‎, ‎then this is called the generalized $k$-rainbow dominating function of a graph $G$‎. ‎The corresponding $\gamma_{gkr}$‎, ‎which is the minimum sum of numbers of assigned colors over all vertices of $G$‎, ‎is called the g$k$-rainbow domination number of $G$‎. ‎In this paper‎, ‎we present a linear algorithms for determining a minimum generalized $2$-rainbow dominating set of a tree and on $GP(n,2)$.

Highlights

 

Article PDF

Keywords


 

Article PDF

 1. T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs,Marcel Dekker, New York, 1998.
2. B.Bresar, T. K. Sumenjak, Note On the 2-rainbow domination in graphs, Discrete Applied Mathematics, Elsevier, 155, 2394–2400 (2007).
3. D. A. Mojdeh, M. Ghanbari, M.Ramezani, domination number in unit disk graph, via s-clique approach, ikpress, 628, 227–236 (2016).
4. T. W. Haynes, S. T. Hedetniemi, P. J. Slater(edds), Domination in Graphs:Advancced Topics, Marcel Dekker, New York, 1998.
5. B. Bresar, M. A. Henning, S. Klavzar, On integer domination in graphs and Vizing-like problems, Taiwanese J. Mathematics, 10, 1317–1328 (2006).
6. M. Ghanbari, D. A. Mojdeh, Restrained 2-rainbow domination of a graph, Submitted (2022).
7. M. Ghanbari, M. Jalinoosi, Upper Bounds for 2-Restrained Dominatiion Number of GP(n,2), Submitted (2022).
8. GH. Shirdel, M. Ghanbbari, M. Ramezani, Semi-Total Roman dominating in graphs, Submitted (2023).
9. B. Hartnel, D. F. Rall, On dominating the Cartesian product of a graph and k2, Discuss. Math. Graph Theory, 24, 389–402 (2004).
10. B. Bresar, M. A. Henning, Douglas F. Rall, Rainbow domination in graphs, Taiwanese J. Mathematics, 213–225 (2008). 
Volume 8, Issue 1
July 2023
Pages 26-30
  • Receive Date: 13 December 2023
  • Revise Date: 05 February 2024
  • Accept Date: 24 February 2024
  • Publish Date: 28 February 2024