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

E. Yıldırım ()

Mathematical Methods of Operations Research, 2010, vol. 71, issue 2, 267-281

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. Copyright Springer-Verlag 2010

Keywords: Maximum clique; Maximum stable set; Stability number; Clique number; Graph spectra; 05C69; 68R10; 15A18 (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-009-0295-4 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:71:y:2010:i:2:p:267-281

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-009-0295-4

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().