Please use this identifier to cite or link to this item:
|Title:||Maximum k-regular induced subgraphs|
|Author:||Cardoso, Domingos M.|
|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.|
|Appears in Collections:||MAT - Artigos|
Files in This Item:
|CardosoLozin2007.pdf||Electronic Version||291.01 kB||Adobe PDF||View/Open Request a copy|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.