Lower bound for the sum of the number of vertices of some subgraphs of a directed graph

Question

Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$.

Let $C(V_i)$ be the union of $V_i$ and all successors of the vertices in $V_i$ (all of them, not only the direct successors).

Is it possible to get a lower bound $f(n)$ for the sum of the sizes of the $C(V_i)$:

$$\sum_{i=1}^{\binom{n}{k}} \vert C(V_i) \vert \ge f(n) \gt k\binom{n}{k}\space ?$$

For example for $k = \lceil n/2 \rceil$, or some other $k = g(n)$?

Answer 1

Consider the graph $G$ with vertices $V=\{1,2,\dots n\}$, and edges $E=\{2\mapsto 1, 3\mapsto 1, \dots, n\mapsto 1\}$. For a given $V_i$, the cardinality of the set $|C(V_i)|$ is $k$ if $1\in V_i$ and $k+1$ otherwise. As there are $\binom{n-1}{k}$ subsets such that $1\notin V_i$, the total sum becomes: $$\sum_{i=1}^{\binom{n}{k}} \vert C(V_i) \vert = k\binom{n}{k}+\binom{n-1}{k}$$

I believe this is the lowest possible sum for a simple weakly connected directed graph, but I do not have a proof for that. Either way, you will not find a stricter lower bound than: $$f(n)=k\binom{n}{k}+\binom{n-1}{k}$$