On Minimal Connected Dominating Sets

Abstract

A connected dominating set is a dominating set \(S\) with the additional property that the subgraph induced by \(S\) is connected. We are interested in the collection C of graphs in which every minimal connected dominating set is of one size.
Trees, for instance, clearly belong to this collection. A partial characterization will be discussed; in particular, we determine those graphs which have the property that all spanning trees have the same number of leaves. It is noted that membership in this sub-collection of C can be determined in polynomial time.