Cactus graphs with unique minimum dominating sets

Abstract

For any graph G and for two subsets X and D of the vertex set of G the set D is an X-dominating set of G, if every vertex of X either is in D or has at least one neighbor in D. If the set X is equal the whole vertex set of G, then an X-dominating set is called a dominating set of G. A dominating set and an X-dominating set of G of minimal cardinality is called a minimum dominating set and a minimum X-dominating set of G, respectively. Gunther, Hartnell, Markus and Rall have characterized all trees with unique minimum dominating sets. In this paper we generalize this result for unique minimum X-dominating sets. Further, a characterization is given for cactus graphs with unique minimum dominating sets.