A lower bound on independence in terms of degrees

DOI10.1016/j.dam.2011.03.003zbMath1218.05036OpenAlexW2020061266MaRDI QIDQ548268

Jochen Harant

Publication date: 28 June 2011

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

Full work available at URL: https://www.db-thueringen.de/servlets/MCRFileNodeServlet/dbt_derivate_00021174/IfM_Preprint_M10_08.pdf

zbMATH Keywords

independencestabilityconnected graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40) Vertex degrees (05C07)

Related Items

Transversals and independence in linear hypergraphs with maximum degree two ⋮ New bounds on the independence number of connected graphs ⋮ On vertex independence number of uniform hypergraphs ⋮ 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 ⋮ The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3 ⋮ Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees

Cites Work

• Independence in connected graphs
• Foreword: Special issue on stability in graphs and related topics
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• A lower bound on the independence number of a graph in terms of degrees
• On the independence number of a graph in terms of order and size