Aproximating the maximum size of a K-regular induced subgraph by an upper bound on the co k-plex number

• Tipo: Artigo em Revista Científica Internacional
• Data: 2010

Autores

C. J. Luz (Autor) Outra

Revista

Título: Journal of Mathematical Sciences

Vol. 182 Nº 2

Páginas: 216-226

ISSN: 1072-3374

Editora: Springer Nature

Classificação Científica

FOS: Ciências exactas e naturais

Outras Informações

Abstract (EN): Let α k and α^k denote respectively the maximum cardinality of a k-regular induced subgraph and the co-k-plex number of a given graph. In this paper, we introduce a convex quadratic programming upper bound on α^k , which is also an upper bound on α k . The new bound denoted by υ^k improves the bound υ k given in [3]. For regular graphs, we prove a necessary and sufficient condition under which υ^k equals υ k . We also show that the graphs for which α^k equals υ^k coincide with those such that α k equals υ k . Next, an improvement of υ^k denoted by ϑ^k is proposed, which is not worse than the upper bound ϑ k for α k introduced in [8]. Finally, some computational experiments performed to appraise the gains brought by ϑ^k are reported.

Idioma: Inglês

Tipo (Avaliação Docente): Científica