Stability with respect to total restrained domination in bipartite graphs

Document Type : Full Length Article

Authors

1 Department of Mathematics, Shabestar Branch, Islamic Azad University, Shabestar, I. R. Iran

2 Department of Mathematics, Shahed University, Tehran, I. R. Iran

Abstract

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.

Keywords

Main Subjects

References

[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

Journal of Discrete Mathematics and Its Applications
Volume 10, Issue 3
September 2025
Pages 263-272

Files

History

  • Receive Date: 28 January 2025
  • Revise Date: 03 March 2025
  • Accept Date: 08 March 2025
  • First Publish Date: 08 July 2025
  • Publish Date: 01 September 2025

Share

How to cite

Statistics