The Turán number of sparse spanning graphs

DOI10.1016/J.JCTB.2013.02.002MaRDI QIDQ744159zbMATHOpenAlexFDO

Authors Noga Alon, Raphael Yuster

Publication date 6 October 2014

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

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)

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.

Cites work

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

Cited in

(9)

• On a packing problem of Alon and Yuster
• Packing large trees of consecutive orders
• Unavoidable hypergraphs
• On the number of sparse connected graphs
• All feedback arc sets of a random Turán tournament have \(\lfloor{n}/{k}\rfloor-{k}+1\) disjoint \({k}\)-cliques (and this is tight)
• The representation number of some sparse graphs
• Seven largest trees pack
• On Erdős-Sós conjecture for trees of large size
• The Turán number for spanning linear forests

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)