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

¹ Azad University

² Shahed University

10.22061/jdma.2025.11697.1113

Abstract

Let $G=(V,E)$ be a graph with no isolated vertices. A subset $D$ of vertices is called a total dominating set (abbreviated TDS) if every vertex of $G$ is adjacent to a vertex in $D$. A TDS $D$ is a total restrained dominating set (abbreviated TRDS) if $D$ has a further property that each vertex outside $D$ is adjacent to a vertex outside $D$. 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 $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 associated decision problem to this variant is NP-hard even when restricted to bipartite graphs. We also determine the total restrained stability number in some families of graphs, including the families of trees and unicyclic graphs.

Graphical Abstract