Optimization Online


Four new upper bounds for the stability number of a graph

Miklos Ujvari(ujvarim***at***cs.elte.hu)

Abstract: In 1979, L. Lovasz defined the theta number, a spectral/semidefinite upper bound on the stability number of a graph, which has several remarkable properties (e.g. it is exact for perfect graphs). The definition of Lovasz's theta number relies on the notion of orthonormal representation of the graph, and, dually, can be obtained by optimizing over the theta body. In the paper we will describe counterparts of theorems due to Wilf, Hoffman, and Lovasz; three spectral and one semidefinite bound on the stability number, obtained via optimizing over a polyhedron of nonnegative matrices, resp. the inverse theta body.


Category 1: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 01/04/2011
Entry Accepted: 01/04/2011
Entry Last Modified: 01/04/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society