Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/4439
Título: | Maximum k-regular induced subgraphs |
Autor: | Cardoso, Domingos M. Kaminski, Marcin Lozin, Vadim |
Palavras-chave: | Graphs Independent sets Induced matchings Hamiltonian cycles |
Data: | 2007 |
Editora: | Springer Verlag |
Resumo: | 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 |
Versão do Editor: | http://www.springerlink.com/content/q510000166707781/ |
Aparece nas coleções: | DMat - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
CardosoLozin2007.pdf | Electronic Version | 291.01 kB | Adobe PDF |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.