## Abstract

A set S of vertices in a graph G is a paired dominating set if every vertex of G is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching (not necessarily as an induced subgraph). The paired domination number, γ_{pr}(G), of G is the minimum cardinality of a paired dominating set of G. A set of vertices whose removal from G produces a graph without isolated vertices is called a non-isolating set. The minimum cardinality of a non-isolating set of vertices whose removal decreases the paired domination number is the γ_{pr}^{−}-stability of G, denoted st^{−}_{γ}_{pr}(G). The paired domination stability of G is the minimum cardinality of a non-isolating set of vertices in G whose removal changes the paired domination number. We establish properties of paired domination stability in graphs. We prove that if G is a connected graph with γ_{pr}(G) ≥ 4, then st^{−}_{γ}_{pr}(G) ≤ 2∆(G) where ∆(G) is the maximum degree in G, and we characterize the infinite family of trees that achieve equality in this upper bound.

Original language | English |
---|---|

Journal | Ars Mathematica Contemporanea |

Volume | 22 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2022 |

## Keywords

- Paired domination
- paired domination stability

## ASJC Scopus subject areas

- Theoretical Computer Science
- Algebra and Number Theory
- Geometry and Topology
- Discrete Mathematics and Combinatorics