| Issue |
RAIRO-Oper. Res.
Volume 59, Number 1, January-February 2025
|
|
|---|---|---|
| Page(s) | 579 - 586 | |
| DOI | https://doi.org/10.1051/ro/2024233 | |
| Published online | 14 February 2025 | |
On the restrained domination stability in graphs
1
Department of Mathematics, Shabestar Branch, Islamic Azad University, Shabestar, Iran
2
Department of Mathematics, Shahed University, Tehran, Iran
* Corresponding author: n.jafarirad@gmail.com
Received:
3
January
2024
Accepted:
28
December
2024
A subset S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. A dominating set S is a restrained dominating set if for each vertex x ∈ V (G) − S there is a vertex y ∈ V (G) − S such that xy ∈ E(G). The restrained domination number of G, denoted by γr(G) is the minimum cardinality of a restrained dominating set of G. The restrained domination stability number of G, denoted by stγr (G), is the minimum number of vertices whose removal changes the restrained domination number of G. In this paper we study the restrained domination stability number of a graph and determine it for several families of graphs. We present bounds for the restrained domination stability number of a graph. We also prove that determining the restrained domination stability number is NP-hard even when restricted to bipartite graphs.
Mathematics Subject Classification: 05C69
Key words: Domination / restrained domination / stability / NP-hard / planar
© The authors. Published by EDP Sciences, ROADEF, SMAI 2025
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.