Paired domination stability in graphs

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

Research output: Contribution to journalArticlepeer-review

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

Fingerprint

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

Cite this