آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 121 |
| تعداد مقالات | 1,448 |
| تعداد مشاهده مقاله | 1,554,419 |
| تعداد دریافت فایل اصل مقاله | 1,458,896 |
Mixed double Roman domination in graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 12، دوره 11، شماره 2، شهریور 2026، صفحه 503-519 اصل مقاله (522.51 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2024.28947.1789 | ||
| نویسندگان | ||
| H. Abdollahzadeh Ahangar* 1؛ M. Chellali2؛ S.M. Sheikholeslami3؛ J.C. Valenzuela Tripodoro4 | ||
| 1Department of Mathematics, Babol Noshirvani University of Technology, Shariati Ave., Babol, I.R. Iran, Postal Code: 47148-71167 | ||
| 2LAMDA-RO Laboratory, Department of Mathematics, University of Blida, Blida, Algeria | ||
| 3Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran | ||
| 4Department of Mathematics, University of Cádiz, Spain | ||
| چکیده | ||
| Let $G=(V,E)$ be a simple graph with vertex set $V$ and edge set $E$. A mixed double Roman dominating function (MDRDF) of $G$ is a function $f:V\cup E \rightarrow \{0,1,2,3\}$ satisfying (1) for any element $x\in V\cup E$ with $f(x)=0$, there must be either element $y\in V\cup E$, with $f(y)=3,$ which is adjacent or incident to $x$, or either two elements $y,z \in V\cup E$, with $f(y),f(z)=2$ which are adjacent or incident to $x$; (2) for any element $x\in V\cup E$ with $f(x)=1$, there must be either element $y\in V\cup E$, with $f(y)\ge 2,$ which is adjacent or incident to $x$. The weight of an MDRDF $f$ is $w(f)=f(V\cup E)=\sum_{x\in V\cup E} f(x)$ and the minimum weight among all the MDRD functions the \textit{MDRD-number}, $\gamma _{dR}^*(G)$, of the graph $G$. In this paper we start the study of this variation of the classic Roman domination problem by setting some basic results, giving exact values and sharp bounds of the MDRD number and we approach the study of the complexity of the decision problem associated to the MDR domination in graphs. | ||
| کلیدواژهها | ||
| Roman domination, double Roman domination؛ mixed 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), no. 4, 1443–1454. https://doi.org/10.1007/s40840-015-0141-1
[2] H. Abdollahzadeh Ahangar, M.A. Henning, V. Samodivkin, and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016), no. 2, 501–517.
[3] M.P. Alvarez-Ruiz, T. Mediavilla-Gradolph, S.M. Sheikholeslami, J.C. Valenzuela-Tripodoro, and I.G. Yero, On the strong Roman domination number of graphs, Discrete Appl. Math. 231 (2017), 44–59. https://doi.org/10.1016/j.dam.2016.12.013
[4] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29. https://doi.org/10.1016/j.dam.2016.03.017 [5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer International Publishing, Cham, 2020, pp. 365–409. [6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984. https://doi.org/10.1016/j.akcej.2019.12.001
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer International Publishing, Cham, 2021, pp. 273–307.
[8] X. Chen, A note on the double Roman domination number of graphs, Czechoslovak Math. J. 70 (2020), no. 1, 205–212. https://doi.org/10.21136/CMJ.2019.0212-18 [9] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22. https://doi.org/10.1016/j.disc.2003.06.004
[10] B. Courcelle, J.A. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst. 33 (2000), no. 2, 125–150. https://doi.org/10.1007/s002249910009
[11] N. Dehgardi, Mixed Roman domination and 2-independence in trees, Commun. Comb. Optim. 3 (2018), no. 1, 79–91. https://doi.org/10.22049/cco.2018.25964.1062 [12] G. Hickey, F. Dehne, A. Rau-Chaplin, and C. Blouin, SPR distance computation for unrooted trees, Evol. Bioinform. 4 (2008), 17–27. https://doi.org/10.4137/EBO.S419
[13] R. Khoeilar, H. Karami, M. Chellali, and S.M. Sheikholeslami, An improved upper bound on the double Roman domination number of graphs with minimum degree at least two, Discrete Appl. Math. 270 (2019), 159–167. https://doi.org/10.1016/j.dam.2019.06.018 [14] M. Liedloff, T. Kloks, J. Liu, and S.L. Peng, Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math. 156 (2008), no. 18, 3400–3415. https://doi.org/10.1016/j.dam.2008.01.011
[15] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Am. Math. Mon. 107 (2000), no. 7, 585–594. https://doi.org/10.1080/00029890.2000.12005243
[16] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), no. 6, 136–138. | ||
|
آمار تعداد مشاهده مقاله: 289 تعداد دریافت فایل اصل مقاله: 532 |
||