### Paired domination stability in graphs

#### 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.

DOI: https://doi.org/10.26493/1855-3974.2522.eb3

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications