connected graph – Optimization Online

A new lower bound on the independence number of a graph

Published: 2009/12/04

Graphs and Matroids connected graph, independence number, min algorithm

For a given connected graph G on n vertices and m edges, we prove that its independence number α(G) is at least ((2m+n+2) -sqrt(sqr(2m+n+2)-16sqr(n)))/8. Article Download View A new lower bound on the independence number of a graph