2
$\begingroup$

Let $G$ be a (connected) graph with $n$ vertices. Is it true that the maximum cardinality of a minimal vertex cover of $G$ is $\geq \frac{n-1}{3}$? If so, can you point out any reference? If not, what is an easy counterexample? Thanks!

Note: In the old version of the question I was asking whether the maximum cardinality of a minimal vertex cover of $G$ is $\geq \lfloor \frac{n}{2} \rfloor$. This is not true in general (consider, for example, a triangle with three whiskers attached to each of its vertices).

$\endgroup$
0
$\begingroup$

Let $\alpha(G)$ and $i(G)$ be the maximum cardinality of a minimal vertex cover of $G$ and the minimum cardinality of a maximal independent set of a graph $G = (V, E)$, respectively. It is known that $$ \alpha(G) + i(G) = |V| = n \tag{$\spadesuit$} \label{eq:1} $$

Motivated by your example, consider a clique $C_k$ of size $k > 1$. For each vertex $v$ of $C_k$, create $k$ new vertices and connect each of them to $v$. In the new graph $G$ obtained, if a maximal independent set contains no vertex of $C_k$, it has size $k^2$; otherwise, it has size $(k - 1)k + 1$. Therefore, $$ i(G) = (k - 1)k + 1 $$ and $$ \alpha(G) = |V| - i(G) = k(k + 1) - i(G) = 2k - 1 $$ By letting $k = 5$, we have $\alpha(G) = 9$ and $n = |V| = 30$, where $$ \alpha(G) < \frac{n-1}{3} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.