Optimization Online


Gap, cosum, and product properties of the $\theta'$ bound on the clique number

Immanuel Bomze (immanuel.bomze***at***univie.ac.at)
Florian Frommlet (florian.frommlet***at***univie.ac.at)
Marco Locatelli (locatelli***at***di.unito.it])

Abstract: In a paper published 1978, McEliece, Rodemich and Rumsey improved Lov\'asz' bound for the Maximum Clique Problem. This strengthening has become well-known under the name Lov\'asz-Schrijver bound and is usually denoted by $\theta'$. This article now deals with situations where this bound is not exact. To provide instances for which the gap between this bound and the actual clique number can be arbitrarily large, we establish homomorphy results for this bound under cosums and products of graphs, and study the special class of circulant graphs: here we show that for circulant graphs of prime order there must be a positive gap between the clique number and the bound.

Keywords: circulant graph, direct graph product, lexicographic graph product, maximum clique problem, semidefinite programming

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical Report TR-ISDS {\bf 2007-06}, University of Vienna, to appear in: Optimization (2010).

Download: [PDF]

Entry Submitted: 04/24/2007
Entry Accepted: 04/25/2007
Entry Last Modified: 03/08/2010

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