Bounds on the independence number of a graph in terms of order, size and maximum degree

DOI10.1016/j.dam.2016.09.021zbMath1358.05222OpenAlexW2527757211MaRDI QIDQ516816

Elahe Sharifi, Nader Jafari Rad

Publication date: 15 March 2017

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

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

zbMATH Keywords

independencetransversalmaximum degree

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• A new lower bound on the independence number of a graph and applications
• An improved lower bound on the independence number of a graph
• A lower bound on independence in terms of degrees
• Lower bounds on the independence number of certain graphs of odd girth at least seven
• Independence in connected graphs
• The independence number in graphs of maximum degree three
• On the independent domination number of regular graphs
• Independent domination in graphs: A survey and recent results
• A new lower bound on the independence number of graphs
• Independence, odd girth, and average degree
• The potential of greed for independence
• New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs
• Sharp bounds on the order, size, and stability number of graphs
• On the independence number of a graph in terms of order and size

This page was built for publication: Bounds on the independence number of a graph in terms of order, size and maximum degree