A new lower bound on the independence number of graphs

DOI10.1016/j.dam.2012.10.001zbMath1262.05114OpenAlexW4285025586MaRDI QIDQ1946229

Christian Laforest, Romain Campigotto, Eric Angel

Publication date: 18 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.10.001

zbMATH Keywords

independence numbervarianceexpectationvertex cover

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

New bounds on the independence number of connected graphs ⋮ On vertex independence number of uniform hypergraphs ⋮ Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives ⋮ Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited ⋮ An improved lower bound on the independence number of a graph ⋮ Bounds on the independence number of a graph in terms of order, size and maximum degree ⋮ Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees

This page was built for publication: A new lower bound on the independence number of graphs