## 5 Minimal Connected Dominating Set Enumeration
We then define  
\[\mathcal{N}^{+}(X)=\{\mu((X\setminus\{v\})\cup W^{*}):v\in X,W^{* }\subseteq V(G),|W^{*}|\leq 3\Delta-2,\] \[G[(X\setminus\{v\})\cup W^{*}]\text{ is a connected dominating set of }G\}.\]  
Applying Lemma 8 for each \(Y\in\mathcal{S}_{\text{cds}}\), there is a set of vertices \(W\subseteq Y\) with cardinality at most \(\Delta\) such that \((X\setminus\{v\})\cup W\) is a dominating set of \(G\). Moreover, by Lemma 9, there is a set of vertices \(U\subseteq Y\) with a cardinality at most \(2\Delta-2\) such that \((X\setminus\{v\})\cup W\cup U\) is a connected dominating set of \(G\). Thus, for each \(Y\in\mathcal{S}_{\text{cds}}\) with \(X\
eq Y\), \(\mathcal{N}^{+}(X)\) has a minimal connected dominating set \(Z\in\mathcal{S}_{\text{cds}}\) such that \(|X\setminus Y|>|Z\setminus Y|\). From Theorem 1, we have the following. Theorem 6: _There is an \(n^{3\Delta+O(1)}\)-delay enumeration algorithm for Minimal Connected Dominating Set Enumeration._  
We would like to mention that a similar improvement for \(d\)-claw free graphs would not be straightforward. In fact, we can show that Minimal Connected Dominating Set Enumeration is at least as hard as Minimal Transversal Enumeration, even on claw-free graphs. A graph is said to be _co-bipartite_ if its complement is bipartite. It is easy to observe that every co-bipartite graph has no independent set of size \(3\), and hence it is claw-free. **Theorem 7**. : _If there is an output-polynomial time (or a polynomial-delay) algorithm for Minimal Connected Dominating Set Enumeration on co-bipartite graphs, then there is an output-polynomial time (or a polynomial-delay) algorithm for enumerating minimal transversals in hypergraphs._  
Proof. : The reduction is in fact identical to one in [8], which proves a similar \"hardness\" of enumerating minimal dominating sets in co-bipartite graphs. Let \(\mathcal{H}=(V,\mathcal{E})\) be a hypergraph. We assume that \(\mathcal{E}\) is nonempty and \(\emptyset\
ot\in\mathcal{E}\) as otherwise the instance is trivial. From the incidence bipartite graph \(\mathcal{H}\) (see Theorem 4), we complete both \(V\) and \(V_{\mathcal{E}}\) into cliques. Then, we add a new vertex \(r\), which is adjacent to all vertices in \(V\). Let \(G\) be the graph obtained in this way. It is easy to see that \(G\) is co-bipartite and has two cliques \(V\cup\{r\}\) and \(V_{\mathcal{E}}\). Observe that every transversal \(S\subseteq V\)of \(\mathcal{H}\) is a connected dominating set of \(G\). This follows from the facts that every vertex in \(V_{\mathcal{E}}\) is adjacent to at least one vertex in \(S\) and every vertex in \(S\) is adjacent to other vertices in \(V\cup\{r\}\). (Our assumption \(\mathcal{E}\
eq\emptyset\) implies that \(S\
eq\emptyset\).) Let \(S\) be a minimal connected dominating set of \(G\). As \(r\) has no neighbors in \(V_{\mathcal{E}}\), \(S\) contains at least one vertex from \(V\cup\{r\}\). Moreover, as \(V_{\mathcal{E}}\
eq\emptyset\) and \(G[S]\) is connected, \(S\) contains at least one vertex from \(V\), implying that \(r\
otin S\) by the minimality of \(S\). Then, observe that either \(S=\{v,w_{e}\}\) for some \(v\in V\) and \(w_{e}\in V_{\mathcal{E}}\) with \(v\in e\) or \(S\subseteq V\). To see this, suppose that \(S\) contains at least one vertex \(w_{e}\) of \(V_{\mathcal{E}}\). Then, as \(S\) contains at least one vertex of \(V\), it contains a vertex \(v\in V\) that is adjacent to \(w_{e}\) in \(G\). Since these two vertices \(v\) and \(w_{e}\) dominate all the vertices in \(G\), by the minimality of \(S\), \(S\) contains no other vertices at all. Using a similar argument used in Theorem 4, \(S\) is a minimal transversal of \(\mathcal{H}\) if \(S\subseteq V\) holds. Now, suppose that there is an output-polynomial time algorithm for Minimal Connected Dominating Set Enumeration. By applying the algorithm to \(G\), we can enumerate all minimal connected dominating sets \(\mathcal{S}\) of \(G\).