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.
Acknowledgments
The authors are grateful to Sergiy Butenko (Texas A&M University), Aaron Clauset (University of Colorado at Boulder) and Vladimir Nikiforov (University of Memphis) for their helpful comments.
Disclosure
No potential conflict of interest was reported by the authors.
Notes
1. Note that several ‘algorithmic’ bounds on 
have been derived [Citation6,Citation11,Citation19,Citation31,Citation44]; however, as in the case of such bounds on , they are out of scope of this paper. Besides, we do not consider lower bounds for special types of graphs, such as bounds on triangle-free graphs [Citation27,Citation28,Citation32,Citation45,Citation46] and others [Citation30].
A. Bossecker and D. Rautenbach, Interpolating between bounds on the independence number, Discret. Math. 310 (2010), pp. 17–18. doi: 10.1016/j.disc.2010.05.026 F. Chung, The average distance and the independence number, J. Graph Theory 2 (1988), pp. 229–235. doi: 10.1002/jgt.3190120213 J.R. Griggs and D.J. Kleitman, Independence and the Havel-Hakimi residue, Discret. Math. 127 (1994), pp. 209–212. doi: 10.1016/0012-365X(92)00479-B Y. Li, C. Rousseau, and W. Zang, The lower bound on independence number, Sci. China (Ser. A) 45 (2002), pp. 64–69. S.M. Selkow, The independence number of graphs in terms of degrees, Discret. Math. 122 (1993), pp. 343–348. doi: 10.1016/0012-365X(93)90307-F D. Kreher and S. Radziszowski, On ramsey graphs: Theoretical and computational results, J. Comb. Math. Comb. Comput. 4 (1988), pp. 37–52. D. Kreher and S. Radziszowski, Minimum triangle-free graphs, Ars Combinatoria 31 (1991), pp. 65–92. C. Löwenstein, A. Pedersen, D. Rautenbach, and F. Regen, Independence, odd girth, and average degree, J. Graph Theory 67 (2011), pp. 96–111. doi: 10.1002/jgt.20518 J.B. Shearer, A note on the independence number of triangle-free graphs, J. Comb. Theory (Ser. B) 53 (1991), pp. 300–307. doi: 10.1016/0095-8956(91)90080-4 W. Staton, Some Ramsey-type numbers and the independence ratio, Trans. Amer. Math. Soc. 256 (1979), pp. 353–370. doi: 10.1090/S0002-9947-1979-0546922-6 Y. Li and Q. Lin, Lower bounds for independence numbers of some locally sparse graphs, J. Comb. Optim. (2012). Additional information
Funding
V. Boginski's research was supported in part by the Air Force Office of Scientific Research grant number FA9550-12-1-0103. This material is based upon work supported by AFRL Mathematical Modeling and Optimization Institute.
![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})