Counting the number of minimal connected supergraphs of an arbitrary disconnected digraph

Question

To start by "connected" in the context of directed graphs, more formally I mean "weakly-connected" in addition by "minimal" I am using the term with respect to the subgraph relation. With that said for any disconnected digraph $G=(V,E)$ we can always find a connected digraph $H=(V,E')$ on the same vertex set $V$ with $E\subseteq E'$ so that $H\supseteq G$ is a connected supergraph of $G$ this can be done by adding arcs to $G$ that connect all of its connected components to form our new directed graph $H$ For example one can visualize this process by my crudely drawn drawn diagram in microsoft-paint:

      

However the digraph $H$ shown above is not minimal with respect to the subgraph relation, because I could have added less arrows to form another connected digraph $H'$ satisfying $G\subseteq H'\subset H$ in particular I could remove one of the two arrows connecting two of the components in $H$ to get $H'$.

Now I want to count the number of minimal, connected, supergraphs of any dissconected graph $G$. Or more formally if for any dissconected graph $G$ one defines a set $Q$ as follows:

$$Q=\small \{D\supseteq G:\left(D\text{ is weakly connected}\right)\land \left(\text{For any digraph }H\text{ we have }G\subseteq H\subseteq D\implies H=D\right)\}$$

Then I want to find the value of $|Q|$, now this shoudn't be hard and I think I know the answer. Yet I'm unsure if I made a slight error in my reasoning. I think $|Q|=2^{|S|-1}|S|!\prod_{C\in S}|\mathcal{V}(C)|$

Where $S$ is the set of connected components in $G$. My reasoning was basically first if we partition the set $V=\mathcal{V}(G)$ into the family $\mathcal{F}=\{\mathcal{V}(C):C\in S\}$ then now if we take any set of distinct representatives from $\mathcal{F}$ we can form a path $P$ of length $|S|-1$ by connecting them together by $|S|-1$ arrows, where the graph $G\cup P$ should be a minimal, connected supergraph as clearly we see $G\subseteq G\cup P$ and removing any of the arrows from $P$ should dissconect $G\cup P$ with that said there are exactly $\prod_{C\in S}|\mathcal{V}(C)|$ distinct representives we can choose from where each should form a different path $P$, moreover when constructing any path we have to order the vertices and since there are $|S|$ of them there will be $|S|!$ different orderings, lastly as each path is directed and by swapping the direction of any arrow in any of the paths this will still leave $G\cup P$ connected thus because there are $|P|=|S|-1$ arcs in our path digraph $P$ we see the number of digraphs formed by swapping the direction of each arc is $2^{|S|-1}$ so there should be exactly $2^{|S|-1}|S|!\prod_{C\in S}|\mathcal{V}(C)|$ different minimally connected supergraphs of $G$. Or equivalently $|Q|=2^{|S|-1}|S|!\prod_{C\in S}|\mathcal{V}(C)|$. So is this correct? Or have I made an error somewhere in my reasoning? Any help/corrections etc. would be appreciated.

Answer 1

If I understood your approach correctly, you are missing a rather big chunk of cases, namely these, where the new connections form a tree rather than just a path. To simplify the problem I would suggest the following:

1. Create a multigraph $\mathcal{G}$ such that its vertices correspond to (weakly) connected components of your graph.
2. Between any pair $(v_1, v_2)$ of vertices $\mathcal{G}$ add labeled edges, where labels are $S_1 \times S_2$ where $S_i$ is the set of vertices representing the connected component of $G$ corresponding to vertex $v_i$ (and the reverse direction will be handled when adding edges for pair $(v_2, v_1)$).
3. Count the number of spanning trees in this multigraph with labeled edges.

If your original graph $G$ has $k$ connected components, this approach gives you the following formula:

$$\sum_{T \in \mathcal{T}_k}\ \ \prod_{\{i,j\} \in T, i < j}2\cdot|S_i|\cdot |S_j| = 2^{k-1}\sum_{T \in \mathcal{T}_k}\ \ \prod_{\{i,j\} \in T, i < j}|S_i|\cdot |S_j|$$ where $\mathcal{T}_k$ is the set of undirected labeled trees on $k$ vertices (the last equality comes from the fact that you always have $k-1$ edges, and each of these can be in one of two directions).

I hope this helps $\ddot\smile$