| Article ID: | iaor1997635 |
| Country: | Netherlands |
| Volume: | 18 |
| Issue: | 3 |
| Start Page Number: | 139 |
| End Page Number: | 145 |
| Publication Date: | Oct 1995 |
| Journal: | Operations Research Letters |
| Authors: | Luz Carlos J. |
| Keywords: | optimization |
The upper bound on the independence number of a undirected graph is presented. The bound is deduced by applying the theory of lagrangian duality to a quadratic formulation of the problem. A characterization of the graphs that attain the proposed bound and a heuristic for approaching the largest independence set of any graph are also given.