scientific article; zbMATH DE number 1990716

MaRDI QIDQ4430882zbMATH OpenFDO

Authors Narsingh Deo, Ying Zhang, Z. Nikoloski

Publication date 13 October 2003

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• A new lower bound on the independence number of graphs
• Bounds on the independence number of a graph in terms of order, size and maximum degree
• Randomly finding independent sets in locally sparse graphs
• An upper bound on the independence number of a graph computable in polynomial-time
• On the independence number of random graphs

Cited in

(4)

• A new lower bound on the independence number of graphs
• Randomly finding independent sets in locally sparse graphs
• Improved replica bounds for the independence ratio of random regular graphs
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph

This page was built for publication:

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