A note on eigenvalue bounds for independence numbers of non-regular graphs

作者：Li Yusheng; Zhang Zhen^*

来源：Discrete Applied Mathematics, 2014, 174: 146-149.

DOI：10.1016/j.dam.2014.04.008

• Simple non-regular graph
• Independence number
• Eigenvalue bound

Let G be a simple connected graph of order n >= 2 with maximum degree Delta and minimum degree delta, and eigenvalues lambda(1) >= lambda(2) >= ... >= lambda(n). It is shown that the independence number of G can be bounded from above by Delta-delta-lambda(n)/Delta n and lambda(1)-lambda(n)+Delta-2 delta/lambda(1)-lambda(n)+Delta-delta n.

• 出版日期2014-9-10
• 单位同济大学