Spectral upper bounds for the order of a k-regular induced subgraph

详细信息    查看全文

• 作者：Domingos M. Cardoso ; Peter Rowlinson
• 关键词：Graph ; Main eigenvalue ; Independence number ; Clique number
• 刊名：Linear Algebra and its Applications
• 出版年：2010
• 出版时间：15 October 2010
• 年：2010
• 卷：433
• 期：5
• 页码：1031-1037
• 全文大小：135 K

文摘

Let G be a simple graph with least eigenvalue λ and let S be a set of vertices in G which induce a subgraph with mean degree k. We use a quadratic programming technique in conjunction with the main angles of G to establish an upper bound of the form Sinf{(k+t)q_G(t):t>-λ} where q_G is a rational function determined by the spectra of G and its complement. In the case k=0 we obtain improved bounds for the independence number of various benchmark graphs.