Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Artigos >
 Spectral upper bounds for the order of a k-regular induced subgraph
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/4234

title: Spectral upper bounds for the order of a k-regular induced subgraph
authors: Cardoso, D.M.
Rowlinson, P.
keywords: Clique number
Main eigenvalue
Independence number
Induced subgraphs
Least eigenvalue
Graph theory
issue date: 2010
publisher: Elsevier
abstract: 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 | S | ≤ inf {(k + t) qG (t) : t > - λ} where qG 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. © 2010 Elsevier Inc. All rights reserved.
URI: http://hdl.handle.net/10773/4234
ISSN: 0024-3795
publisher version/DOI: http://www.sciencedirect.com/science/article/pii/S0024379510002065
source: Linear Algebra and Its Applications
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
LAA10624.pdfVersão Electrónica283.04 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2