A simpler characterization of a spectral lower bound on the clique number

Research output: Contribution to journalArticlepeer-review

Abstract

Given a simple, undirected graph G, Budinich (Discret Appl Math 127:535-543, 2003) proposed a lower bound on the clique number of G by combining the quadratic programming formulation of the clique number due to Motzkin and Straus (Can J Math 17:533-540, 1965) with the spectral decomposition of the adjacency matrix of G. This lower bound improves the previously known spectral lower bounds on the clique number that rely on the Motzkin-Straus formulation. In this paper, we give a simpler, alternative characterization of this lower bound. For regular graphs, this simpler characterization allows us to obtain a simple, closed-form expression of this lower bound as a function of the positive eigenvalues of the adjacency matrix. Our computational results shed light on the quality of this lower bound in comparison with the other spectral lower bounds on the clique number.

Original languageEnglish
Pages (from-to)267-281
Number of pages15
JournalMathematical Methods of Operations Research
Volume71
Issue number2
DOIs
Publication statusPublished - 1 Apr 2010

Keywords

  • Clique number
  • Graph spectra
  • Maximum clique
  • Maximum stable set
  • Stability number

Fingerprint

Dive into the research topics of 'A simpler characterization of a spectral lower bound on the clique number'. Together they form a unique fingerprint.

Cite this