Harant, J.; Schiermeyer, I. On the independence number of a graph in terms of order and size. (English) Zbl 1030.05091 Discrete Math. 232, No. 1-3, 131-138 (2001). 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. Cited in 1 ReviewCited in 25 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) PDFBibTeX XMLCite \textit{J. Harant} and \textit{I. Schiermeyer}, Discrete Math. 232, No. 1--3, 131--138 (2001; Zbl 1030.05091) Full Text: DOI