×

On the independence number of a graph in terms of order and size. (English) Zbl 1030.05091

Summary: For the independence number \(\alpha(G)\) of a connected graph \(G\) on \(n\) vertices with \(m\) edges the inequality \(\alpha(G)\geq {1\over 2} [(2m+ n+ 1)-\sqrt{(2m+ n+ 1)^2- 4n^2}]\) is proved and its algorithmic realization is discussed.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI