Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T14:30:35.493Z Has data issue: false hasContentIssue false
  • English
  • Français

Degree Powers in Graphs: The Erdős–Stone Theorem

Published online by Cambridge University Press:  02 February 2012

BÉLA BOLLOBÁS  and
VLADIMIR NIKIFOROV
BÉLA BOLLOBÁS
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WB, UK (e-mail: b.bollobas@dpmms.cam.ac.uk) Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA (e-mail: vnikifrv@memphis.edu)
VLADIMIR NIKIFOROV
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA (e-mail: vnikifrv@memphis.edu)
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 1 ≤ p ≤ r + 1, with r ≥ 2 an integer, and let G be a graph of order n. Let d(v) denote the degree of a vertex v ∈ V(G). We show that if$\[ \sum_{v\in V (G) }d^{p} (v) > (1-1/r) ^{p}n^{p+1}, \]$then G has more than$\[ \frac{1}{2^{6r (r+1) }r^{r}}n^{r-1} \]$(r + 1)-cliques sharing a common edge. From this we deduce that if$\[ \sum_{v\in V (G) }d^{p} (v) >(1-1/r) ^{p}n^{p+1}+C, \]$then G contains more than$\[ \frac{C}{p2^{6r (r+1) +1}r^{r}}n^{r-p} \]$cliques of order r + 1.

In turn, this statement is used to strengthen the Erdős–Stone theorem by using ∑v ∈ V(G)dp(v) instead of the number of edges.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 89 - 105
Copyright
Copyright © Cambridge University Press 2012

References

[1]Bollobás, B. (1998) Modern Graph Theory, Vol. 184 of Graduate Texts in Mathematics, Springer.Google Scholar
[2]Bollobás, B. and Nikiforov, V. (2004) Degree powers in graphs with forbidden subgraphs. Electron. J. Combin. 11 R42.CrossRefGoogle Scholar
[3]Bollobás, B. and Nikiforov, V. (2008) Joints in graphs. Discrete Math. 308 9–19.CrossRefGoogle Scholar
[4]Caro, Y. and Yuster, R. (2000) A Turán type problem concerning the powers of the degrees of a graph. Electron. J. Combin. 7 R47.CrossRefGoogle Scholar
[5]Caro, Y. and Yuster, R. A Turán type problem concerning the powers of the degrees of a graph (revised). Preprint. arXiv:math/0401398v1Google Scholar
[6]Erdős, P. (1970) On the graph theorem of Turán (in Hungarian). Mat. Lapok 21 249–251.Google Scholar
[7]Nikiforov, V. (2008) Graphs with many r-cliques have large complete r-partite subgraphs. Bull. London Math. Soc. 40 23–25.CrossRefGoogle Scholar
[8]Nikiforov, V. (2009) Degree powers in graphs with forbidden even cycle. Electron. J. Combin. 11 R107.CrossRefGoogle Scholar
[9]Nikiforov, V. (2009) Stability for large forbidden subgraphs. J. Graph Theory 62 362–368.CrossRefGoogle Scholar
[10]Nikiforov, V. and Rousseau, C. C. (2009) Ramsey goodness and beyond. Combinatorica 29 227–262.CrossRefGoogle Scholar
[11]Pikhurko, O. Remarks on a paper of Y. Caro and R. Yuster on Turán problem. Preprint. arXiv:math.CO/0101235v1Google Scholar
[12]Pikhurko, O. and Taraz, A. (2005) Degree sequences of F-free graphs. Electron. J. Combin. 12 R69CrossRefGoogle Scholar