New analytical lower bounds on the clique number of a graph

References

• W. Aiello, F. Chung, and L. Lu, A Random Graph Model for Massive Graphs, in Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000, pp. 171–180.
   Google Scholar
• N. Alon and J. Spencer, The Probabilistic Method, Wiley, New York, 1992.
   Google Scholar
• A.L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286 (1999), pp. 509–512. doi: 10.1126/science.286.5439.509
   PubMed Web of Science ®Google Scholar
• C. Berge, Problèmes de coloration en théorie des graphes(in french), Publ. Inst. Stat. Univ. Paris 9 (1960), pp. 123–160.
   Google Scholar
• I.M. Bomze, M. Budinich, P.M. Pardalos, and M. Pelillo, The Maximum Clique Problem, in Handbook of Combinatorial Optimization, Ding-Zhu Du and Panos M. Pardalos, eds., Springer, Dordrecht, 1999, pp. 1–74.
   Google Scholar
• 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
   Web of Science ®Google Scholar
• R. Brooks, On coloring the nodes of a network, Proc Cambridge Philos. Soc. 37 (1941), pp. 194–197.
   Google Scholar
• M. Budinich, Exact bounds on the order of the maximum clique of a graph, Discret. Appl. Math. 127 (2003), pp. 535–543. doi: 10.1016/S0166-218X(02)00386-4
   Web of Science ®Google Scholar
• S.R. Bulò and M. Pelillo, New bounds on the clique number of graphs based on spectral hypergraph theory, Learn. Intell. Optim. (2009), pp. 45–58. doi: 10.1007/978-3-642-11169-3_4
   Google Scholar
• Y. Caro, New results on the independence number, Technical Report, 1979.
   Google Scholar
• F. Chung, The average distance and the independence number, J. Graph Theory 2 (1988), pp. 229–235. doi: 10.1002/jgt.3190120213
   Web of Science ®Google Scholar
• F. Chung and L. Lu, Connected components in random graphs with given expected degree sequences, Ann. Comb. (2002), pp. 125–145. doi: 10.1007/PL00012580
   Google Scholar
• F. Chung and L. Lu, The average distance in a random graph with given expected degrees, Internet Math. 1 (2003), pp. 91–113. doi: 10.1080/15427951.2004.10129081
   Google Scholar
• A. Clauset, C.R. Shalizi, and M.E.J. Newman, Power-law distributions in empirical data, SIAM Rev. 51 (2009), pp. 661–703. doi: 10.1137/070710111
   Web of Science ®Google Scholar
• D. Cvetković, M. Doob, and H. Sachs, Spectra of Graphs, Academic Press, New York, 1980.
   Google Scholar
• T.A. Davis and Y. Hu, University of Florida sparse matrix collection, ACM Trans. Math. Softw. 38 (2011), pp. 1:1–1:25, http://www.cise.ufl.edu/research/sparse/matrices.
   Web of Science ®Google Scholar
• C.S. Edwards and C.H. Elphick, Lower bounds for the clique and the chromatic numbers of a graph, Discret. Appl. Math. 5 (1983), pp. 51–64. doi: 10.1016/0166-218X(83)90015-X
   Web of Science ®Google Scholar
• P. Erdös and A. Rényi, On the Evolution of Random Graphs, Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 1960, pp. 17–61.
   Google Scholar
• 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
   Web of Science ®Google Scholar
• J. Harant, A lower bound on the independence number of a graph, Discret. Math. 188 (1998), pp. 239–243. doi: 10.1016/S0012-365X(98)00048-X
   Web of Science ®Google Scholar
• J. Harant and D. Rautenbach, Independence in connected graphs, Discret. Appl. Math. 159 (2011), pp. 79–86. doi: 10.1016/j.dam.2010.08.029
   Web of Science ®Google Scholar
• J. Harant and I. Schiermeyer, On the independence number of a graph in terms of order and size, Discret. Math. 232 (2001), pp. 131–138. doi: 10.1016/S0012-365X(00)00298-3
   Web of Science ®Google Scholar
• J. Håstad, Clique is hard to approximate within , in Foundations of Computer Science, 1996. Proceedings, 37th Annual Symposium on IEEE, Burlington, VT, 1996, pp. 627–636.
   Google Scholar
• M. Hofmeister, Graph radius and degree sequence, Math. Nachr. 139 (1988), pp. 37–44. doi: 10.1002/mana.19881390105
   Web of Science ®Google Scholar
• S. Janson, T. Łuczak, and I. Norros, Large cliques in a power-law random graph, J. Appl. Probab. 47 (2010), pp. 1124–1135. doi: 10.1239/jap/1294170524
   Web of Science ®Google Scholar
• R.M. Karp, Reducibility Among Combinatorial Problems, Springer, New York, 1972.
   Google Scholar
• D. Kreher and S. Radziszowski, On ramsey graphs: Theoretical and computational results, J. Comb. Math. Comb. Comput. 4 (1988), pp. 37–52.
   Google Scholar
• D. Kreher and S. Radziszowski, Minimum triangle-free graphs, Ars Combinatoria 31 (1991), pp. 65–92.
   Web of Science ®Google Scholar
• L. Li, D. Alderson, J. Doyle, and W. Willinger, Towards a theory of scale-free graphs: Definition, properties, and implications, Internet Math. 2 (2005). doi: 10.1080/15427951.2005.10129111
   Google Scholar
• Y. Li and Q. Lin, Lower bounds for independence numbers of some locally sparse graphs, J. Comb. Optim. (2012).
   Web of Science ®Google Scholar
• Y. Li, C. Rousseau, and W. Zang, The lower bound on independence number, Sci. China (Ser. A) 45 (2002), pp. 64–69.
   Google Scholar
• 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
   Web of Science ®Google Scholar
• T.S. Motzkin and E.G. Straus, Maxima for graphs and a new proof of a theorem of Turan, Can. J. Math. 17 (1965), pp. 533–540. doi: 10.4153/CJM-1965-053-6
   Web of Science ®Google Scholar
• O. Murphey, Lower bounds on the stability number of graphs computed in terms of degrees, Discret. Math. 90 (1991), pp. 207–211. doi: 10.1016/0012-365X(91)90357-8
   Web of Science ®Google Scholar
• M.E.J. Newman, Assortative mixing in networks, Phys. Rev. Lett. 89 (2002), pp. 208701.
   PubMed Web of Science ®Google Scholar
• M.E.J. Newman, The structure and function of complex networks, SIAM Rev. 45 (2003), pp. 167–256. doi: 10.1137/S003614450342480
   Web of Science ®Google Scholar
• M. Newman, Networks: An Introduction, Oxford University Press, Inc., New York, 2010.
   Google Scholar
• V. Nikiforov, Some inequalities for largest eigenvalue of a graph, Comb, Probab. Comput. 11 (2002), pp. 179–189. doi: 10.1017/S0963548301004928
   Web of Science ®Google Scholar
• V. Nikiforov, Eigenvalues and forbidden subgraphs i, Linear Algebra Appl. 422 (2007), pp. 284–290. doi: 10.1016/j.laa.2006.10.007
   Web of Science ®Google Scholar
• V. Nikiforov, More spectral bounds on the clique and independence numbers, J. Comb. Theory, Ser. B 99 (2009), pp. 819–826. doi: 10.1016/j.jctb.2009.01.003
   Web of Science ®Google Scholar
• P.R.J. Östergård, A fast algorithm for the maximum clique problem, Discret. Appl. Math. 120 (2002), pp. 197–207. doi: 10.1016/S0166-218X(01)00290-6
   Web of Science ®Google Scholar
• J. Pattillo, N. Youssef, and S. Butenko, On clique relaxation models in network analysis, Eur. J. Oper. Res. 226 (2013), pp. 9–18. doi: 10.1016/j.ejor.2012.10.021
   Web of Science ®Google Scholar
• D.D.S. Price, A general theory of bibliometric and other cumulative advantage processes, J. Amer. Soc. Inf. Sci. (1976), pp. 292–306. doi: 10.1002/asi.4630270505
   Web of Science ®Google Scholar
• 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
   Web of Science ®Google Scholar
• 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
   Web of Science ®Google Scholar
• 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
   Web of Science ®Google Scholar
• P. Turan, On an extremal problem in graph theory (in hungarian), Math. Fiz. Lapok 48 (1941), pp. 436–452.
   Google Scholar
• A. Veremyev and V. Boginski, Identifying large robust network clusters via new compact formulations of maximum k-club problems, Eur. J. Oper. Res. 218 (2012), pp. 316–326. doi: 10.1016/j.ejor.2011.10.027
   Web of Science ®Google Scholar
• V. Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum 81-11217-9, 1981.
   Google Scholar
• H.S . Wilf, Spectral bounds for the clique and independence numbers of graphs, J. Comb. Theory, Ser. B 40 (1986), pp. 113–117. doi: 10.1016/0095-8956(86)90069-9
   Web of Science ®Google Scholar
• R. Xulvi-Brunet and I.M. Sokolov, Reshuffling scale-free networks: From random to assortative, Phys. Rev. E 70 (2004), pp. 066102. doi: 10.1103/PhysRevE.70.066102
   Web of Science ®Google Scholar