## 5 Minimal Connected Dominating Set Enumeration  
To enumerate all the minimal connected dominating sets, we use the same strategy in the previous section. Let \(G\) be a connected graph with maximum degree \(\Delta\) and let \(\mathcal{S}_{\text{cds}}\) be the collection of all minimal connected dominating sets of \(G\). Let \(X,Y\in\mathcal{S}_{\text{cds}}\) be distinct minimal connected dominating sets of \(G\). Then, there is a vertex \(v\in X\setminus Y\). Lemma 8: _There is a vertex set \(W\subseteq Y\) of size at most \(\Delta\) such that \((X\setminus\{v\})\cup W\) is a dominating set of \(G\). Moreover, \(G[(X\setminus\{v\})\cup W]\) has at most \(\Delta\) components._  
Proof: Since \(X\) is a dominating set of \(G\), each vertex in \(V(G)\setminus N[v]\) belongs to \(X\setminus\{v\}\) or has a neighbor in \(X\setminus\{v\}\). As \(v\
otin Y\), \(Y\) contains at least one vertex \(v^{\prime}\) in \(N(v)\). Moreover, for each \(w\in N(v)\setminus(X\cup\{v^{\prime}\})\), \(Y\) contains at least one vertex \(w^{\prime}\) in \(N[w]\). We let \(W=\{v^{\prime}\}\cup\{w^{\prime}:w\in N(v)\setminus(X\cup\{v^{\prime}\})\}\). Clearly, \(W\) contains at most \(|N(v)\setminus X|\leq\Delta\) vertices. Each vertex in \(N[v]\) belongs to \((X\setminus\{v\})\cup W\) or has a neighbor in \((X\setminus\{v\})\cup W\). This implies that \((X\setminus\{v\})\cup W\) is a dominating set of \(G\). Since \(G[X]\) is connected, \(G[(X\setminus\{v\})]\) has at most \(|N(v)\cap X|\) components. As \(|W|\leq|N(v)\setminus X|\), \(G[(X\setminus\{v\}\cup W]\) has at most \(|N(v)\cap X|+|N(v)\setminus X|\leq\Delta\) components. Let \(W\) be a set of vertices of size at most \(\Delta\) discussed in Lemma 8 and let \(X^{\prime}=(X\setminus\{v\})\cup W\) be a dominating set of \(G\). Since \(Y\) is a dominating set of \(G\), the following observation holds. Proposition 5: _For each component \(C\) of \(G[X^{\prime}]\), \(N[C]\cap Y\
eq\emptyset\)._  
Lemma 9: _Let \(S\subseteq V\) be an arbitrary dominating set of \(G\) and let \(Y\) be a minimal connected dominating set of \(G\). Then, there is a vertex set \(U\subseteq Y\) of at most \(2q-2\) vertices such that \(G[S\cup U]\) is connected, where \(q\) is the number of connected components in \(G[S]\)._  
Proof: We prove the lemma by induction on the number of connected components \(q\) in \(G[S]\). If \(G[S]\) is connected, we have finished. Suppose otherwise. Let \(C\) and \(C^{\prime}\) be distinct components in \(G[S]\). As both \(N[C]\cap Y\) and \(N[C^{\prime}]\cap Y\) are nonempty (by Proposition 5), there is a path \(P\) in \(G[Y]\) connecting \(N[C]\cap Y\) and \(N[C^{\prime}]\cap Y\). We choose \(C\) and \(C^{\prime}\) to minimize the length of such a path \(P\). The path \(P\) contains at most two vertices of \(V\setminus S\) as otherwise one of the internal vertices of \(P\) has no neighbor in \(S\), contradicting the fact that \(S\) is a dominating set of \(G\). Let \(w,w^{\prime}\) be these (possibly identical) two vertices of \(V(P)\cap(V\setminus S)\). Applying the induction to \(S\cup\{w,w^{\prime}\}\) proves the lemma. Thus, there is a set \(U\subseteq Y\) of size at most \(2\Delta-2\) such that \(G[X^{\prime}\cup U]\) is a connected dominating set of \(G\). As \(v\in X\setminus Y\) and \(W\cup U\subseteq Y\), we have  
\[|X\setminus Y|>|(X\setminus\{v\})\setminus Y|=|((X\setminus\{v\})\cup W) \setminus Y|=|(X^{\prime}\cup U)\setminus Y|\geq|Z\setminus Y|,\]  
where \(Z\) is an arbitrary minimal connected dominating set of \(G\) with \(Z\subseteq X^{\prime}\cup U\). Now, let us formally define \(\mathcal{N}^{+}(X)\) for \(X\in\mathcal{S}_{\text{cds}}\). For connected dominating set \(D\) of \(G\), we let \(\mu(D)\) be an arbitrary minimal connected dominating set of \(G\) with \(\mu(D)\subseteq D\). Using Proposition 1, \(\mu(D)\) can be computed in polynomial time.