پیوندهای مفید
آمار
| تعداد نشریات | 13 |
| تعداد شمارهها | 238 |
| تعداد مقالات | 2,418 |
| تعداد مشاهده مقاله | 3,962,364 |
| تعداد دریافت فایل اصل مقاله | 2,874,086 |
Stability with respect to total restrained domination in bipartite graphs | ||
| Journal of Discrete Mathematics and Its Applications | ||
| دوره 10، شماره 3، آذر 2025، صفحه 263-272 اصل مقاله (279.06 K) | ||
| نوع مقاله: Full Length Article | ||
| شناسه دیجیتال (DOI): 10.22061/jdma.2025.11697.1113 | ||
| نویسندگان | ||
| Akbar Azami Aghdash1؛ Nader Jafari Rad* 2؛ Bahram Vakili1 | ||
| 1Department of Mathematics, Shabestar Branch, Islamic Azad University, Shabestar, I. R. Iran | ||
| 2Department of Mathematics, Shahed University, Tehran, I. R. Iran | ||
| تاریخ دریافت: 09 بهمن 1403، تاریخ بازنگری: 13 اسفند 1403، تاریخ پذیرش: 18 اسفند 1403 | ||
| چکیده | ||
| In a graph $G = (V, E)$ with no isolated vertices, a subset $D$ of vertices is said to be a total dominating set (abbreviated TDS) if it has the property that every vertex of $G$ is adjacent to some vertex in $D$. A TDS $D$ is said to be a total restrained dominating set (abbreviated TRDS) if it has a further property that any vertex in $V-D$ is also adjacent to a vertex in $V-D$. Given the isolate-free graph $G$, the total restrained domination number of $G$, which we denote it by $\gamma_{tr}(G)$, is the minimum cardinality of a TRDS of $G$. The minimum number of vertices of the graph $G$ whose removal changes the total restrained domination number of $G$ is called the total restrained domination stability number of $G$, and is denoted by $st_{\gamma_{tr}}(G)$. In this paper we study this variant in bipartite graphs. We show that the related decision problem related to this variant is NP-hard in bipartite graphs. We also determine the total restrained stability number in some families of graphs, including the families of trees and unicyclic graphs. | ||
| کلیدواژهها | ||
| total dominating set؛ total restrained dominating set؛ bipartite graph | ||
| مراجع | ||
|
[1] A. Azami Aghdash, N. Jafari Rad, B. Vakili, On the restrained domination stability in graphs, Rairo Oper. Res. 59 (2025) 579–586. https://doi.org/10.1051/ro/2024233 [2] D. Bauer, F. Harary, J. Nieminen and C. Suffel, Domination alternation sets in graphs, Discrete Math. 47 (1983) 153–161. https://doi.org/10.1016/0012-365X(83)90085-7 [3] T. Burton, D. Sumner, Domination dot-critical graphs, Discrete Math. 306 (2006) 11–18. https://doi.org/10.1016/j.disc.2005.06.029 [4] X. Chen, J. Liu, J. Meng, Total restrained domination in graphs, Comput. Math. Appl. 62 (2011) 2892–2898. https://doi.org/10.1016/j.camwa.2011.07.059 [5] J. Cyman, J. Raczek, On the total restrained domination number of a graph, Australas. J. Combin. 36 (2006) 91–100 https://ajc.maths.uq.edu.au/pdf/36/ajc v36 p091.pdf [6] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the theory of NPCompleteness, Freeman, San Francisco, 1979. https://doi.org/10.1137/1024022 [7] P. J. P. Grobler, C. M. Mynhardt, Secure domination critical graphs, Discrete Math. 309(19) (2009) 5820–5827. https://doi.org/10.1016/j.disc.2008.05.050 [8] M. Hajian, N. Jafari Rad, On the Roman domination stable graphs, Discuss. Math. Graph Theory 37 (2017) 859–871. https://doi.org/10.7151/dmgt.1975 [9] A. Hansberg, N. Jafari Rad, L. Volkmann, Vertex and edge critical Roman domination in graphs, Util. Math. 92 (2013) 73–88. https://utilitasmathematica.com /index.php/Index /article/view/1001 [10] J. H. Hattingh, E. Jonck, E. J. Joubert, A.R. Plummer, Total restrained domination in trees, Discrete Math. 307 (2007) 1643–1650. https://doi.org/10.1016/j.disc.2006.09.014 [11] M. A. Henning, N. Jafari Rad, On total domination critical graphs of high connectivity, Discrete Appl. Math. 157 (2009) 1969–1973. https://doi.org/10.1016/j.dam.2008.12.009 [12] N. Jafari Rad, E. Sharifi, M. Krzywkowski, Domination stability in graphs, Discrete Math. 339 (7)(2016) 1909–1914. https://doi.org/10.1016/j.disc.2015.12.026 [13] H. Jiang, L. Kang, Total restrained domination number in claw-free graph, J. Comb. Optim. 19(2010) 60–68. https://doi.org/10.1007/s10878-008-9161-1 [14] D. Ma, X. Chen, L. Sun, On total restrained domination in graphs, Czechoslovak Math. J. 55 (130) (2005) 165–173. https://doi.org/10.1007/s10587-005-0012-2 [15] D. A. Mojdeh, P. Firoozi, R. Hasni, On connected (γ, k)-critical graphs, Australas. J. Comb. 46 (2010) 25–36. https://ajc.maths.uq.edu.au/pdf/46/ajc v46 p025.pdf [16] D. A. Mojdeh, S. R. Musawi, E. Nazari, Domination critical Knodel graphs, Iranian J. Sci. Tech., Transactions A: Science 43 (2019) 2423–2428. https://doi.org/10.1007/s40995-019-00710-8 | ||
|
آمار تعداد مشاهده مقاله: 367 تعداد دریافت فایل اصل مقاله: 317 |
||