A connected dominating set is a dominating set
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.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.