Paired domination stability in graphs

Aleksandra Gorzkowska, Michael A. Henning, Monika Pilśniak, Elżbieta Tumidajewicz

Research output: Contribution to journalArticlepeer-review


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 languageEnglish
JournalArs Mathematica Contemporanea
Issue number2
Publication statusPublished - 2022


  • Paired domination
  • paired domination stability

ASJC Scopus subject areas

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


Dive into the research topics of 'Paired domination stability in graphs'. Together they form a unique fingerprint.

Cite this