A new lower bound on the independence number of a graph

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

For a given connected graph G on n vertices and m edges, we prove that its independence number is at least (2m+n+2-sqrt(sqr(2m+n+2)-16sqr(n)))/8.
4 pages

Keywords

Discrete Mathematics, F.2.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/131979

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0706.2575
 http://arxiv.org/abs/0706.2575

Collections

arXiv