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

title: Spectral upper bounds on the size of k-regular induced subgraphs
authors: Cardoso, D.M.
Pinheiro, S.J.
keywords: 2-factors
graph spectra
independent sets
induced matchings
programming involving graphs
issue date: 2009
publisher: Elsevier
abstract: Convex quadratic programming upper bounds on the size of k-regular induced subgraphs are analyzed and a necessary and sufficient condition for such upper bounds being tight is introduced. Based on this approach, new spectral upper bounds on the order of maximum size k-regular induced subgraphs are deduced. Related open problems and a few computational experiments are presented. © 2009 Elsevier B.V. All rights reserved.
URI: http://hdl.handle.net/10773/4254
ISSN: 1571-0653
publisher version/DOI: http://www.sciencedirect.com/science/article/pii/S1571065309000031
source: Electronic Notes in Discrete Mathematics
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
CardosoPinheiro2009.pdfElectronic Version232.42 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