The Turán number of sparse spanning graphs

DOI10.1016/J.JCTB.2013.02.002zbMATH Open1301.05201arXiv1404.1182OpenAlexW2115557450MaRDI QIDQ744159FDOQ744159

Authors: Noga Alon, Raphael Yuster 

Publication date: 6 October 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: For a graph $H$, the {em 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 $delta(H)>0$ and $Delta(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 $Delta(H)lesqrtn/200$, then $ex(n,H)=n-1choose2+delta(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=C_n$, 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.

Full work available at URL: https://arxiv.org/abs/1404.1182

zbMATH Keywords

maximum vertex degreeDirac-type resultsexact thresholdminimum vertex degreeTurán-type results

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Density (toughness, etc.) (05C42)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Packings of graphs and applications to computational complexity
• Subgraphs of graphs. I
• Hamiltonian chains in hypergraphs
• Steiner system and large non-Hamiltonian hypergraphs
• On extremal hypergraphs for Hamiltonian cycles
• Edge disjoint placement of graphs
• Extremal graph packing problems: Ore-type versus Dirac-type
• Arc coverings of graphs

Cited In (9)

• Unavoidable hypergraphs
• Packing large trees of consecutive orders
• On a packing problem of Alon and Yuster
• The representation number of some sparse graphs
• Seven largest trees pack
• All Feedback Arc Sets of a Random Turán Tournament Have $\lfloor {n}/{k}\rfloor-{k}+1$ Disjoint ${k}$-Cliques (and This Is Tight)
• On Erdős-Sós conjecture for trees of large size
• The Turán number for spanning linear forests
• On the number of sparse connected graphs

This page was built for publication: The Turán number of sparse spanning graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744159)