New analytical lower bounds on the clique number of a graph. (4th March 2017)

• Record Type: Journal Article
• Authors: Stozhkov, Vladimir; Pastukhov, Grigory; Boginski, Vladimir; Pasiliao, Eduardo L.
• Is Part Of: Optimization methods and software. Volume 32:Number 2(2017)
• Page Start: 336
• Page End: 368
• Publication Date: 2017-03-04
• Subjects: clique number -- Motzkin–Straus formulation -- spectral graph theory -- assortativity coefficient -- Erdös-Rényi model -- power-law graphs; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1172578
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : This paper proposes three new analytical lower bounds on the clique number of a graph and compares these bounds with those previously established in the literature. Two proposed bounds are derived from the well-known Motzkin–Straus quadratic programming formulation for the maximum clique problem. Theoretical results on the comparison of various bounds are established. Computational experiments are performed on random graph models such as the Erdös-Rényi model for uniform graphs and the generalized random graph model for power-law graphs that simulate graphs with different densities and assortativity coefficients. Computational results suggest that the proposed new analytical bounds improve the existing ones on many graph instances.