The generous Roman domination number

Document Type : Research Paper

Authors

1 RECITS Laboratory, Faculty of Sciences UZA, Djelfa, Algeria

2 Department of Mathematics, University of Blida, Blida, Algeria

3 Department of Mathematics, University of M´ed´ea, M´ed´ea, Algeria

Abstract

Let $G=(V,E)$\ be a simple graph and $f:V\rightarrow\{0,1,2,3\}$ be a function. A vertex $u$ with $f\left( u\right) =0$ is called an undefended vertex with respect to $f$ if it is not adjacent to a vertex $v$ with $f(v)\geq2.$ We call the function $f$ a generous Roman dominating function (GRDF) if for every vertex with $f\left( u\right) =0$ there exists at least a vertex $v$ with $f(v)\geq2$ adjacent to $u$ such that the function $f^{\prime}:V\rightarrow \{0,1,2,3\}$, defined by $f^{\prime}(u)=\alpha$, $f^{\prime}(v)=f(v)-\alpha$ where $\alpha=1$ or $2$, and $f^{\prime}(w)=f(w)$ if $w\in V-\{u,v\}$ has no undefended vertex. The weight of a generous Roman dominating function $f$ is the value $f(V)=\sum_{u\in V}f(u)$. The minimum weight of a generous Roman dominating function on a graph $G$\ is called the generous Roman domination number of $G$, denoted by $\gamma_{gR}\left( G\right) $. In this paper, we initiate the study of generous Roman domination and show its relationships. Also, we give the exact values for paths and cycles. Moreover, we present an upper bound on the generous Roman domination number, and we characterize cubic graphs $G$ of order $n$ with $\gamma_{gR}\left( G\right) =n-1$, and a Nordhaus-Gaddum type inequality for the parameter is also given. Finally, we study the complexity of this parameter.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, T. W. Haynes and J. C. Valenzuela-Tripodoro, Mixed Roman domination in graphs, Bull. Malays. Math. Sci. Soc., 40 (2017) 1443–1454.
[2] M. Adabi, E. E. Targhi, N. J. Rad and M. S. Moradi, Properties of independent Roman domination in graphs, Australas. J. Combin., 52 (2012) 11–18.
[3] H. Abdollahzadeh Ahangar, M. Chellali and S. M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math., 232 (2017) 1–7.
[4] R. A. Beeler, T. W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math., 211 (2016) 23–29.
[5] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, Varieties of Roman domination, in: Structures of Domination in Graphs, edited by T. W. Haynes, S. T. Hedetniemi and M. A. Henning, Springer, Berlin/Heidelberg, (2021) 273–307.
[6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb., 17 (2020) 966–984.
[7] M. Chellali and N. Jafari Rad, A note on the independent Roman domination in unicyclic graphs, Opuscula Math., 32 (2012) 715–718.
[8] E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Math., 278 (2004) 11–22.
[9] E. J. Cockayne, O. Favaron and C. M. Mynhardt, Secure domination, weak Roman domination and forbid-den subgraphs, Bull. Inst. Combin. Appl., 39 (2003) 87–100.
[10] M. Garey and D. Johnson, ”A guide to the theory of NP-completeness”. Computers and intractability. Freeman, New York (1979).
[11] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of domination in graphs, Monographs and Textbooks in Pure and Applied Mathematics, 208, Marcel Dekker, Inc., New York, 1998.
[12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in graphs: advanced topics, Marcel Dekker, New York, 1998.
[13] S. T. Hedetniemi and M. A. Henning, Defending the Roman Empire — A new strategy, Discrete Math., 266 (2003) 239–251.
[14] C.-H. Liu and G. J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim., 26 (2013) 608–619.
[15] P. Roushini Leely Pushpam and T. N. M. Malini Mai, Edge Roman domination in graphs, J. Combin. Math. Combin. Comput., 69 (2009) 175–182.

Files

History

  • Receive Date: 24 October 2021
  • Revise Date: 31 May 2023
  • Accept Date: 08 June 2023
  • Published Online: 01 June 2024

Share

How to cite

Statistics