Minimal Connected Dominating Set

A minimal connected dominating set of a graph is a connected dominating set that is inclusion-minimal within the family of connected dominating sets. In other words, no proper subset of is also a connected dominating set (Lokshtanov et al. 2018).

Equivalently, is a minimal connected dominating set iff for every , either is no longer a dominating set or the induced subgraph is a disconnected graph. Structurally, each therefore either has a private vertex, meaning a vertex dominated by and by no other vertex of , or is a cut vertex of (Golovach et al. 2020).

This is not the same as a minimal dominating set that happens to induce a connected subgraph. For example, in the path graph PathGraph[Range[5]], is a minimal connected dominating set. Removing 3 leaves , which remains a dominating set, but is a disconnected graph. Thus, is not a minimal dominating set.

A minimum connected dominating set, by contrast, has smallest cardinality among all connected dominating sets (Sampathkumar and Walikar 1979). Every minimum connected dominating set is inclusion-minimal, but an inclusion-minimal connected dominating set need not have smallest possible cardinality.

Precomputed minimal connected dominating sets for many named graphs, together with their counts, are available in the Wolfram Language as GraphData[graph, "MinimalConnectedDominatingSets"], GraphData[graph, "MinimalConnectedDominatingSetCount"]. The corresponding minimal connected domination polynomial is available as GraphData[graph, "MinimalConnectedDominationPolynomial"][x]. The coefficient of in this polynomial is the number of minimal connected dominating sets of cardinality .