The generous Roman domination number

Mohammed, Benatallah; Blidia, Mostafa; Ouldrabah, Lyes

doi:10.22108/toc.2023.131167.1928

تعداد نشریات	43
تعداد شماره‌ها	1,682
تعداد مقالات	13,775
تعداد مشاهده مقاله	32,268,810
تعداد دریافت فایل اصل مقاله	12,764,710

	The generous Roman domination number
Transactions on Combinatorics
مقاله 8، دوره 13، شماره 2، شهریور 2024، صفحه 179-196 اصل مقاله (562.33 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2023.131167.1928
نویسندگان
Benatallah Mohammed^* ¹؛ Mostafa Blidia²؛ Lyes Ouldrabah³
¹RECITS Laboratory, Faculty of Sciences UZA, Djelfa, Algeria
²Department of Mathematics, University of Blida, Blida, Algeria
³Department of Mathematics, University of M´ed´ea, M´ed´ea, Algeria
چکیده
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.
کلیدواژه‌ها
Roman domination؛ Weak Roman domination؛ Double Roman domination

مراجع
[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.
آمار تعداد مشاهده مقاله: 325 تعداد دریافت فایل اصل مقاله: 304

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

The generous Roman domination number