Hostname: page-component-669899f699-b58lm Total loading time: 0 Render date: 2025-05-02T02:57:24.749Z 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*
Affiliation:
School of Mathematics, University of Birmingham, Birmingham, B15 2TT, UK (e-mail: s.a.lo@bham.ac.uk)

Abstract

Letkr(n, δ) be the minimum number ofr-cliques in graphs withn vertices and minimum degree at least δ. We evaluatekr(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 onn, δ andr).

Keywords

Type
Paper
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

[1]Andrásfai,B.,Erdős,P. andSós,V. T. (1974)On the connection between chromatic number, maximal clique and minimal degree of a graph.Discrete Math.8205–218.CrossRefGoogle Scholar
[2]Bollobás,B. (1976)On complete subgraphs of different orders.Math. Proc. Cambridge Philos. Soc.7919–24.CrossRefGoogle Scholar
[3]Erdős,P. (1969)On the number of complete subgraphs and circuits contained in graphs.Časopis Pěst. Mat.94290–296.CrossRefGoogle Scholar
[4]Fisher,D. (1989)Lower bounds on the number of triangles in a graph.J. Graph Theory13505–512.CrossRefGoogle Scholar
[5]Lo,A. S. L. (2009)Triangles in regular graphs with density below one half.Combin. Probab. Comput.18435–440.CrossRefGoogle Scholar
[6]Lo,A. S. L. (2010) Cliques in graphs. PhD thesis, University of Cambridge.Google Scholar
[7]Lovász,L. andSimonovits,M. (1983) On the number of complete subgraphs of a graph II. InStudies 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.3631599–1618.CrossRefGoogle Scholar
[9]Razborov,A. A. (2007)Flag algebras.J. Symbolic Logic721239–1282.CrossRefGoogle Scholar
[10]Razborov,A. A. (2008)On the minimal density of triangles in graphs.Combin. Probab. Comput.17603–618.CrossRefGoogle Scholar
[11]Turán,P. (1941)Eine Extremalaufgabe aus der Graphentheorie.Mat. Fiz. Lapok48436–452.Google Scholar