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

Document Type : Original Research Article

Authors

1 University of Qom

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 arbitry 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 γgkr, which is the minimum sum of numbers of assigned colores over all vertices of G, is called the gk-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).

Keywords


 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 29-35
  • Receive Date: 13 December 2023
  • Revise Date: 05 February 2024
  • Accept Date: 24 February 2024
  • Publish Date: 01 November 2023