Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/4439
Title: Maximum k-regular induced subgraphs
Author: 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.
Peer review: yes
URI: http://hdl.handle.net/10773/4439
ISSN: 1382-6905
Publisher Version: http://www.springerlink.com/content/q510000166707781/
Appears in Collections:MAT - Artigos

Files in This Item:
File Description SizeFormat 
CardosoLozin2007.pdfElectronic Version291.01 kBAdobe PDFView/Open    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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