Stability with respect to total restrained domination in bipartite graphs

Articles in Press

Document Type : Full Length Article

Authors

1 Azad University

2 Shahed University

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.

Keywords

Main Subjects

Journal of Discrete Mathematics and Its Applications

Articles in Press, Accepted Manuscript
Available Online from 08 July 2025

Files

History

  • Receive Date: 28 January 2025
  • Accept Date: 08 March 2025
  • Publish Date: 08 July 2025

Share

How to cite

Statistics