Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-02-12T03:13:22.107Z Has data issue: false hasContentIssue false
  • English
  • Français

Cliques in Graphs With Bounded Minimum Degree

Published online by Cambridge University Press:  26 January 2012

ALLAN LO
ALLAN LO*
Affiliation:
School of Mathematics, University of Birmingham, Birmingham, B15 2TT, UK (e-mail: s.a.lo@bham.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let kr(n, δ) be the minimum number of r-cliques in graphs with n vertices and minimum degree at least δ. We evaluate kr(n, δ) for δ ≤ 4n/5 and some other cases. Moreover, we give a construction which we conjecture to give all extremal graphs (subject to certain conditions on n, δ and r).

Keywords

05C35
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 3 , May 2012 , pp. 457 - 482
Copyright
Copyright © Cambridge University Press 2012

References

[1]Andrásfai, B., Erdős, P. and Sós, V. T. (1974) On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math. 8 205–218.CrossRefGoogle Scholar
[2]Bollobás, B. (1976) On complete subgraphs of different orders. Math. Proc. Cambridge Philos. Soc. 79 19–24.CrossRefGoogle Scholar
[3]Erdős, P. (1969) On the number of complete subgraphs and circuits contained in graphs. Časopis Pěst. Mat. 94 290–296.CrossRefGoogle Scholar
[4]Fisher, D. (1989) Lower bounds on the number of triangles in a graph. J. Graph Theory 13 505–512.CrossRefGoogle Scholar
[5]Lo, A. S. L. (2009) Triangles in regular graphs with density below one half. Combin. Probab. Comput. 18 435–440.CrossRefGoogle Scholar
[6]Lo, A. S. L. (2010) Cliques in graphs. PhD thesis, University of Cambridge.Google Scholar
[7]Lovász, L. and Simonovits, M. (1983) On the number of complete subgraphs of a graph II. In Studies in Pure Mathematics, Birkhäuser, pp. 459–495.CrossRefGoogle Scholar
[8]Nikiforov, V. (2011) The number of cliques in graphs of given order and size. Trans. Amer. Math. Soc. 363 1599–1618.CrossRefGoogle Scholar
[9]Razborov, A. A. (2007) Flag algebras. J. Symbolic Logic 72 1239–1282.CrossRefGoogle Scholar
[10]Razborov, A. A. (2008) On the minimal density of triangles in graphs. Combin. Probab. Comput. 17 603–618.CrossRefGoogle Scholar
[11]Turán, P. (1941) Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 436–452.Google Scholar