Skip to main content
1 of 2
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.

MegaTom
  • 136
  • 4