Repositório Institucional da Universidade de Aveiro > Departamento de Matem├ítica > MAT - Artigos >
 Maximum k-regular induced subgraphs
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/4439

title: Maximum k-regular induced subgraphs
authors: Cardoso, Domingos M.
Kaminski, Marcin
Lozin, Vadim
keywords: Graphs
Independent sets
Induced matchings
Hamiltonian cycles
issue date: 2007
publisher: Springer Verlag
abstract: Independent sets, induced matchings and cliques are examples of regular induced subgraphs in a graph. In this paper, we prove that finding a maximum cardinality k-regular induced subgraph is an NP-hard problem for any fixed value of k. We propose a convex quadratic upper bound on the size of a k-regular induced subgraph and characterize those graphs for which this bound is attained. Finally, we extend the Hoffman bound on the size of a maximum 0-regular subgraph (the independence number) from k = 0 to larger values of k.
URI: http://hdl.handle.net/10773/4439
ISSN: 1382-6905
publisher version/DOI: http://www.springerlink.com/content/q510000166707781/
source: Journal of Combinatorial Optimization
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
CardosoLozin2007.pdfElectronic Version291.01 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