The Turán number of sparse spanning graphs

Noga Alon, Raphael Yuster

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

For a graph H, the extremal number ex(n, H) is the maximum number of edges in a graph of order n not containing a subgraph isomorphic to H. Let δ(H)>0 and δ(H) denote the minimum degree and maximum degree of H, respectively. We prove that for all n sufficiently large, if H is any graph of order n with δ(H)≤n/40, then ex(n,H)=(n-12)+δ(H)-1. The condition on the maximum degree is tight up to a constant factor. This generalizes a classical result of Ore for the case H=Cn, and resolves, in a strong form, a conjecture of Glebov, Person, and Weps for the case of graphs. A counter-example to their more general conjecture concerning the extremal number of bounded degree spanning hypergraphs is also given.

Original languageEnglish (US)
Pages (from-to)337-343
Number of pages7
JournalJournal of Combinatorial Theory. Series B
Volume103
Issue number3
DOIs
StatePublished - May 1 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Packing
  • Spanning subgraph
  • Turan number

Fingerprint Dive into the research topics of 'The Turán number of sparse spanning graphs'. Together they form a unique fingerprint.

  • Cite this