Number of bounded minimum vertex covers

Minimum Vertex Cover problem

Input: $G=(V,E)$ and Parameter $k$

Output: Decide whether there exists minimum vertex cover of size at most $k$.

Question:- Can we bound the number of minimum vertex covers of size at most $k$ on general graphs?

C=number of minimum vertex covers of size at most $k$

Is C bounded by $f(k)$? If not can you provide example? If yes what is $f(k)$

• Do you really mean the number of minimum vertex covers of size at most k, or do you mean the number of vertex covers of size at most k? Nov 28 '16 at 9:09
• i.e C= number of minimum vertex covers of size at most $k$. What is the value of C in f(k).
– GOLD
Nov 28 '16 at 9:15
• crossposted from stackoverflow after less than 3 hours without mentioning that on either site ​ ​
– user6973
Nov 30 '16 at 5:29

The number of inclusion-minimal vertex covers of size at most $k$ is at most $2^k$: They can be enumerated by a search tree algorithm that initially has a budget of $k$, then branches as long as the graph contains an edge $\{u,v\}$ into the two cases to add either $u$ or $v$ to the vertex cover. Each branch can be solved recursively and the parameter $k$ is reduced by one in each case.
The number of minimal vertex covers of size at most $k$ obviously bounds the number of minimum vertex covers of size at most $k$ as well.