Hostname: page-component-f554764f5-246sw Total loading time: 0 Render date: 2025-04-11T22:23:02.332Z 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
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)

Abstract

Let 1 ≤p ≤r + 1, withr ≥ 2 an integer, and letG be a graph of ordern. Letd(v) denote the degree of a vertexv ∈V(G). We show that ifthenG has more than(r + 1)-cliques sharing a common edge. From this we deduce that ifthenG contains more thancliques of orderr + 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.

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]Bollobás,B. (1998)Modern Graph Theory, Vol. 184 of Graduate Texts in Mathematics,Springer.Google Scholar
[2]Bollobás,B. andNikiforov,V. (2004)Degree powers in graphs with forbidden subgraphs.Electron. J. Combin.11R42.CrossRefGoogle Scholar
[3]Bollobás,B. andNikiforov,V. (2008)Joints in graphs.Discrete Math.3089–19.CrossRefGoogle Scholar
[4]Caro,Y. andYuster,R. (2000)A Turán type problem concerning the powers of the degrees of a graph.Electron. J. Combin.7R47.CrossRefGoogle Scholar
[5]Caro,Y. andYuster,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. Lapok21249–251.Google Scholar
[7]Nikiforov,V. (2008)Graphs with manyr-cliques have large completer-partite subgraphs.Bull. London Math. Soc.4023–25.CrossRefGoogle Scholar
[8]Nikiforov,V. (2009)Degree powers in graphs with forbidden even cycle.Electron. J. Combin.11R107.CrossRefGoogle Scholar
[9]Nikiforov,V. (2009)Stability for large forbidden subgraphs.J. Graph Theory62362–368.CrossRefGoogle Scholar
[10]Nikiforov,V. andRousseau,C. C. (2009)Ramsey goodness and beyond.Combinatorica29227–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. andTaraz,A. (2005)Degree sequences ofF-free graphs.Electron. J. Combin.12R69CrossRefGoogle Scholar