Stability with respect to total restrained domination in bipartite graphs

Azami Aghdash, Akbar; Jafari Rad, Nader; Vakili, Bahram

doi:10.22061/jdma.2025.11697.1113

Stability with respect to total restrained domination in bipartite graphs

Document Type : Full Length Article

Authors

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

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

10.22061/jdma.2025.11697.1113

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