Skip to main content
added 259 characters in body
Source Link
MegaTom
  • 136
  • 4

Not without some restriction onConsider the graph $G$ with vertices $V=\{1,2,\dots n\}$, and edges $E=\{2\mapsto 1, 3\mapsto 1, \dots, n\mapsto 1\}$. Note thatFor a given $V_i$, ifthe cardinality of the set $G$$|C(V_i)|$ is an empty graph (with n vertices$k$ if $1\in V_i$ and $k+1$ otherwise. As there are $\binom{n-1}{k}$ subsets such that $1\notin V_i$, but no edges) then the you havetotal sum becomes: $$\sum_{i=1}^{\binom{n}{k}} \vert C(V_i) \vert = \sum_{i=1}^{\binom{n}{k}} \vert V_i \vert = k\binom{n}{k}$$$$\sum_{i=1}^{\binom{n}{k}} \vert C(V_i) \vert = k\binom{n}{k}+\binom{n-1}{k}$$

SoI $k\binom{n}{k}$believe this is the lowest possible sum for a lower boundsimple weakly connected directed graph, but to get anything stricterI do not have a proof for that. Either way, you will need some constraint on the graph.not find a stricter lower bound than: $$f(n)=k\binom{n}{k}+\binom{n-1}{k}$$

Not without some restriction on the graph. Note that, if $G$ is an empty graph (with n vertices, but no edges) then the you have: $$\sum_{i=1}^{\binom{n}{k}} \vert C(V_i) \vert = \sum_{i=1}^{\binom{n}{k}} \vert V_i \vert = k\binom{n}{k}$$

So $k\binom{n}{k}$ is a lower bound, but to get anything stricter, you will need some constraint on the graph.

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}$$

Source Link
MegaTom
  • 136
  • 4

Not without some restriction on the graph. Note that, if $G$ is an empty graph (with n vertices, but no edges) then the you have: $$\sum_{i=1}^{\binom{n}{k}} \vert C(V_i) \vert = \sum_{i=1}^{\binom{n}{k}} \vert V_i \vert = k\binom{n}{k}$$

So $k\binom{n}{k}$ is a lower bound, but to get anything stricter, you will need some constraint on the graph.