Paired domination stability in graphs
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.
Articles in this journal are published under Creative Commons Attribution 4.0 International License