Independence in connected graphs

DOI10.1016/j.dam.2010.08.029zbMath1208.05098OpenAlexW2031081001MaRDI QIDQ617904

Jochen Harant, Dieter Rautenbach

Publication date: 14 January 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_00018947/IfM_Preprint_M09_31.pdf

zbMATH Keywords

independencestabilityconnected graph

Mathematics Subject Classification ID

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

Related Items (13)

Transversals and independence in linear hypergraphs with maximum degree two ⋮ A lower bound on the independence number of a graph in terms of degrees and local clique sizes ⋮ New bounds on the independence number of connected graphs ⋮ Extremal values of the chromatic number for a given degree sequence ⋮ On vertex independence number of uniform hypergraphs ⋮ Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives ⋮ Partitions of graphs into small and large sets ⋮ 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 ⋮ New potential functions for greedy independence and coloring ⋮ A lower bound on independence in terms of degrees ⋮ The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3 ⋮ New analytical lower bounds on the clique number of a graph

Cites Work

• Unnamed Item
• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• A dense infinite Sidon sequence
• On Turan's theorem for sparse graphs
• A note on the independence number of triangle-free graphs. II
• Foreword: Special issue on stability in graphs and related topics
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Some Ramsey-Type Numbers and the Independence Ratio
• 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

This page was built for publication: Independence in connected graphs