I have found this lower bound for the size of minimal vertex cover (and proved it).

If a simple connected graph G on n vertices has largest and smallest eigenvalues $\lambda_1,\lambda_n$, respectively, and $\theta_{n-1}$ is the second smallest Laplace eigenvalue, then $$ \tau(G)\geq\frac{n\theta_{n-1}^{2}}{\theta_{n-1}^{2}-4\lambda_{1}\lambda_{n}} $$ When $\tau(G)$ is the minimal size of minimal vertex cover.

I checked it for some graphs and it was very tight for most of them. There are some graphs for which the estimation is not close, but I think it works pretty well most times.

I tried to look for it and didn't find anything. Anyone saw that before? Are there better bounds?



1 Answer 1


I found a better bound for regular graphs- the Hoffmann bound:

Let G be a d-regular graph on $n$ vertices with minimal eigenvalue $\lambda_{min}$. Then $$ \alpha\left(G\right)\leq\frac{-n\lambda_{min}}{d-\lambda_{min}} $$

It is known that for a graph $G$ on $n$ vertices, $\alpha\left(G\right)+\tau\left(G\right)=n$. Thus $$ \tau\left(G\right)\geq\frac{nd}{d-\lambda_{min}} $$

For regular graphs, this bound is always tighter than mine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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