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.