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: | DMat - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
CardosoLozin2007.pdf | Electronic Version | 291.01 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.