Paired domination stability in graphs - Gorzkowska, Aleksandra (Ars mathematica contemporanea, 2022)
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.
Keywords: paired domination; paired domination stability; parna dominacija; stabilnost parne dominacije