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?


Thank!



Is this lower bound for the size of minimal vertex cover new/interesting?
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.


