Lower bounds on the independence number of certain graphs of odd girth at least seven

DOI10.1016/J.DAM.2010.10.011zbMATH Open1203.05121OpenAlexW1978042415WikidataQ114191534 ScholiaQ114191534MaRDI QIDQ617649FDOQ617649

Authors: Anders Sune Pedersen, Dieter Rautenbach, Friedrich Regen 

Publication date: 21 January 2011

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

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

Recommendations

• A lower bound on the independence number of a graph
• The independence number of graphs with large odd girth
• A new lower bound on the independence number of graphs
• A lower bound on the independence number of a graph in terms of degrees
• scientific article; zbMATH DE number 1112370
• On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7
• A new lower bound on the independence number of a graph and applications
• An improved lower bound on the independence number of a graph
• Bounds on the lower size of a 7-critical graph
• The independence number of dense graphs with large odd girth

zbMATH Keywords

independencestabilityodd girth

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Size and independence in triangle‐free graphs with maximum degree three
• Some simplified NP-complete graph problems
• A note on the independence number of triangle-free graphs. II
• Large independent sets in regular graphs of large girth
• Some Ramsey-Type Numbers and the Independence Ratio
• A new proof of the independence ratio of triangle-free cubic graphs
• Independence, odd girth, and average degree
• The independence number of dense graphs with large odd girth
• Locally dense independent sets in regular graphs of~large~girth -- an example of a new approach
• The independence number of graphs with large odd girth

Cited In (7)

• Adjacency eigenvalues of graphs without short odd cycles
• Bounds on the independence number of a graph in terms of order, size and maximum degree
• On the independence numbers of the cubes of odd cycles
• Graphs with odd girth at least seven and high minimum degree
• An improved lower bound on the independence number of a graph
• Independence, odd girth, and average degree
• New bounds on the independence number of connected graphs

This page was built for publication: Lower bounds on the independence number of certain graphs of odd girth at least seven

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q617649)