5
$\begingroup$

Can the number of minimal vertex covers of a graph be super-polynomial (like exponential)? I suspect it can, but can't think of any examples.

Vertex cover $C$ of a graph $G$ is a subset of its vertices that any edge has an incident vertex in that set. That is: $$ C\subseteq V(G) \hspace{1cm} \text{s.t.} \hspace{1cm} \forall_{xy\in E(G)} x\in C \vee y\in C $$

Minimal vertex cover $C$ of a graph $G$ is a vertex cover of $G$ such that the set $C'$obtained by removal of any vertex from $C$ is not a vertex cover of $G$. That is: $$ C \text{ is a vertex cover} \hspace{1cm} \wedge \hspace{1cm} \forall_{v\in C}C':= C-v \text{ is not a vertex cover} $$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

The union of $k$ triangles has $3^k$ minimum vertex covers. You can easily find connected examples.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The union of $k$ edges (the graph $kK_2$) has $2^k$ many minimum vertex covers, or $2^{n/2}$ many where $n$ is the number of vertices. $\endgroup$
    – John Kemeny
    Commented Sep 3, 2013 at 11:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .