Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/5485| Title: | Spectral upper bounds on the size of k-regular induced subgraphs |
| Author: | Cardoso, Domingos Pinheiro, Sofia |
| Keywords: | graph spectra independent sets induced matchings programming involving graphs 2-factors |
| 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. |
| Peer review: | yes |
| URI: | http://hdl.handle.net/10773/5485 |
| ISSN: | 1571-0653 |
| Appears in Collections: | DMat - Artigos |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| SpectralUpperBounds.pdf | 118.15 kB | Adobe PDF |  |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.