A New Lower Bound on the Independence Number of Graphs

Angel, Eric; Campigotto, Romain; Laforest, Christian

Angel, Eric; Campigotto, Romain; Laforest, Christian (2013), A New Lower Bound on the Independence Number of Graphs, Discrete Applied Mathematics, 161, 6, p. 847-852. http://dx.doi.org/10.1016/j.dam.2012.10.001

View/Open

publi1818.pdf (145.6Kb)

Type

Article accepté pour publication ou publié

Date

2013

Journal name

Discrete Applied Mathematics

Volume

161

Number

Publisher

Elsevier

Pages

847-852

Abstract (EN)

We propose a new lower bound on the independence number of a graph. We show that our bound compares favorably to recent ones (e .g . [1 2]). We obtain our bound by using the Bhatia-Davis inequality applied with analytic al results (minimum, maximum, expectation and variance ) of an algorithm for the vertex cover problem.

Subjects / Keywords

vertex cover; expectation; variance; graphs; independence number