The generous Roman domination number

Mohammed, Benatallah; Blidia, Mostafa; Ouldrabah, Lyes

doi:10.22108/toc.2023.131167.1928

تعداد نشریات	42
تعداد شماره‌ها	1,510
تعداد مقالات	12,450
تعداد مشاهده مقاله	24,642,353
تعداد دریافت فایل اصل مقاله	10,411,900

	The generous Roman domination number
Transactions on Combinatorics
مقالات آماده انتشار، اصلاح شده برای چاپ، انتشار آنلاین از تاریخ 18 خرداد 1402 اصل مقاله (560.32 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.
آمار تعداد مشاهده مقاله: 153 تعداد دریافت فایل اصل مقاله: 75

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

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

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

آمار

The generous Roman domination number