
تعداد نشریات | 5 |
تعداد شمارهها | 116 |
تعداد مقالات | 1,348 |
تعداد مشاهده مقاله | 1,354,448 |
تعداد دریافت فایل اصل مقاله | 1,296,514 |
Total double Roman domination stability in graphs | ||
Communications in Combinatorics and Optimization | ||
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 20 خرداد 1404 اصل مقاله (386.54 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2025.30402.2453 | ||
نویسندگان | ||
Ziqiang Xu1؛ Saeed Kosari* 2؛ M. Esmaeili3؛ Aysha Khan4؛ Lutz Volkmann5 | ||
1Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China | ||
2Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China | ||
3Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran | ||
4University of Technology and Applied Sciences, Musannah, Oman | ||
5RWTH Aachen, 52056 Aachen, Germany | ||
چکیده | ||
Let $G$ be a graph with vertex set $V(G)$. A total double Roman dominating function (TDRD-function) on a graph $G$ with no isolated vertices is a function $f :V(G)\to \{0, 1, 2, 3\}$ satisfying the conditions: $(i)$ if $f(v)=0$, then the vertex $v$ must be adjacent to at least two vertices assigned $2$ or one vertex assigned $3$ under $f$, and if $f(v)=1$, then the vertex $v$ must be adjacent to at least one vertex assigned $2$ or $3$ and $(ii)$ the subgraph of $G$ induced by the set $\{v \in V(G) \mid f(v)\neq 0\}$ has no isolated vertices. The weight of a TDRD-function $f$ is the sum of its function values over all vertices, and the minimum weight of a TDRD-function on $G$ is the total double Roman domination number, $\gamma_{tdR}(G)$. The $\gamma_{tdR}$-stability ($\gamma^-_{tdR}$-stability, $\gamma^+_{tdR}$-stability) of $G$, denoted by ${\rm st}_{\gamma_{tdR}}(G)$ (resp. ${\rm st}^-_{\gamma_{tdR}}(G)$, ${\rm st}^+_{\gamma_{tdR}}(G)$), is defined as the minimum size of a set of vertices whose removal changes (resp. decreases, increases) the total double Roman domination number. In this paper, we first determine the exact values of the $\gamma_{tdR}$-stability of some special classes of graphs, and then we present some bounds on ${\rm st}_{\gamma_{tdR}}(G)$, ${\rm st}^-{\gamma_{tdR}}(G)$ and ${\rm st}^+_{\gamma_{tdR}}(G)$). In particular, for a graph $G$ with maximum degree $\Delta\ge 3$, we show that ${\rm st}^-_{\gamma_{tdR}}(G)\leq \Delta-1$. | ||
کلیدواژهها | ||
total double Roman domination؛ total double Roman domination stability | ||
مراجع | ||
[1] A.A. Aghdash, N. Jafari Rad, and B.V. Fasaghandisi, On the restrained domination stability in graphs, RAIRO Oper. Res. 59 (2025), no. 1, 579–586. https://doi.org/10.1051/ro/2024233
[2] M. Akhoundi, A. Khan, J. Shafi, and L. Volkmann, Quasi total double Roman domination in trees, Commun. Comb. Optim. 9 (2024), no. 1, 159–168. https://doi.org/10.22049/cco.2023.29008.1809
[3] D. Bauer, F. Harary, J. Nieminen, and C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983), 153–161. https://doi.org/10.1016/0012-365X(83)90085-7
[4] 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.
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. 115 (2020), 141–171.
[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, The Roman domatic problem in graphs and digraphs: A survey, Discuss. Math. Graph Theory 42 (2022), no. 3, 861–891.
[8] 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. [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] M. Hajian and N. Jafari Rad, On the Roman domination stable graphs, Discuss. Math. Graph Theory 37 (2017), no. 4, 859–871. http://dx.doi.org/10.7151/dmgt.1975
[11] G. Hao, L. Volkmann, and D.A. Mojdeh, Total double Roman domination in graphs, Commun. Comb. Optim. 5 (2020), no. 1, 27–39. https://doi.org/10.22049/cco.2019.26484.1118
[12] G. Hao, Z. Xie, S.M. Sheikholeslami, and M. Hajjari, Bounds on the total double Roman domination number of graphs, Discuss. Math. Graph Theory 43 (2023), no. 4, 1033–1061. https://doi.org/10.7151/dmgt.2417
[13] N. Jafari Rad, E. Sharifi, and M. Krzywkowski, Domination stability in graphs, Discrete Math. 339 (2016), no. 7, 1909–1914. https://doi.org/10.1016/j.disc.2015.12.026
[14] 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
[15] S.M. Sheikholeslami, M. Esmaeili, and L. Volkmann, Outer independent double Roman domination stability in graphs, Ars Combin. 160 (2024), 21–29. http://dx.doi.org/10.61091/ars-160-04
[16] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), no. 6, 136–138.
[17] A. Teymourzadeh and D.A. Mojdeh, Covering total double Roman domination in graphs, Commun. Comb. Optim. 8 (2023), no. 1, 115–125. https://doi.org/10.22049/cco.2021.27443.1265 | ||
آمار تعداد مشاهده مقاله: 32 تعداد دریافت فایل اصل مقاله: 47 |