A New Lower Bound on the Independence Number of Graphs
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
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow full item record
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 / Keywordsvertex cover; expectation; variance; graphs; independence number
Showing items related by title and author.
Explicit lower bounds for the cost of fast controls for some 1-D parabolic or dispersive equations, and a new lower bound concerning the uniform controllability of the 1-D transport–diffusion equation Lissy, Pierre (2015) Article accepté pour publication ou publié
Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem Grosso, Andrea; Della Croce, Federico; Paschos, Vangelis (2004) Article accepté pour publication ou publié