Graphs with Unique Minimum Paired-Dominating Set

Abstract

Let $G=(V,E)$ be a graph without isolated vertices. A set $D\subseteq V$ is a paired-dominating set if $D$ is a dominating set of $G$ and the induced subgraph $G[D]$ has a perfect matching. In this paper, we provide a characterization for block graphs with a unique minimum paired-dominating set. Furthermore, we also establish a constructive characterization for trees with a unique minimum paired-dominating set.