New Analytical Lower Bounds On The Clique Number Of A Graph

Keywords

assortativity coefficient; clique number; Erdös-Rényi model; Motzkin–Straus formulation; power-law graphs; spectral graph theory

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.

Publication Date

3-4-2017

Publication Title

Optimization Methods and Software

Volume

32

Issue

2

Number of Pages

336-368

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1080/10556788.2016.1172578

Socpus ID

84965057371 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84965057371

This document is currently not available here.

Share

COinS