A note on eigenvalue bounds for independence numbers of non-regular graphs ?
Let G G be a simple connected graph of order n?2 n ? 2 with maximum degree ? ? and minimum degree ? ? , and eigenvalues ?1??2????n ? 1 ? ? 2 ? ? ? ? n . It is shown that the independence number of G G can be bounded from above by ? ? ? ? ? n ? n and ? 1 ? ? n + ? ? 2 ? ? 1 ? ? n + ? ? ? n .
eigenvalue bound independence number simple non-regular graph