TY - JOUR

T1 - The Turán number of sparse spanning graphs

AU - Alon, Noga

AU - Yuster, Raphael

N1 - Funding Information:
E-mail addresses: nogaa@tau.ac.il (N. Alon), raphy@research.haifa.ac.il (R. Yuster). 1 Research supported in part by an ERC advanced grant, by a USA–Israeli BSF grant, and by the Israeli I-Core program.

PY - 2013/5

Y1 - 2013/5

N2 - 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.

AB - 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.

KW - Packing

KW - Spanning subgraph

KW - Turan number

UR - http://www.scopus.com/inward/record.url?scp=84877138545&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877138545&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2013.02.002

DO - 10.1016/j.jctb.2013.02.002

M3 - Article

AN - SCOPUS:84877138545

VL - 103

SP - 337

EP - 343

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 3

ER -