Spanning Trees in Dense Graphs

János Komlós; Gábor N. Sárközy; Endre Szemerédi

doi:10.1017/s0963548301004849

Spanning Trees in Dense Graphs

János Komlós, Gábor N. Sárközy, Endre Szemerédi

SAS - Mathematics

Research output: Contribution to journal › Article › peer-review

24 Scopus citations

Abstract

In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n₀ such that, if n ≥ n₀, T is a tree of order n and maximum degree at most cn/log n, and G is a graph of order n and minimum degree at least (1/2 + δ)n, then T is a subgraph of G.

Original language	English (US)
Pages (from-to)	397-416
Number of pages	20
Journal	Combinatorics Probability and Computing
Volume	10
Issue number	5
DOIs	https://doi.org/10.1017/s0963548301004849
State	Published - 2001

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/s0963548301004849

Fingerprint Dive into the research topics of 'Spanning Trees in Dense Graphs'. Together they form a unique fingerprint.

Cite this

@article{93934c458193469f9aeab33d17ac87c1,

title = "Spanning Trees in Dense Graphs",

abstract = "In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n0 such that, if n ≥ n0, T is a tree of order n and maximum degree at most cn/log n, and G is a graph of order n and minimum degree at least (1/2 + δ)n, then T is a subgraph of G.",

author = "J{\'a}nos Koml{\'o}s and S{\'a}rk{\"o}zy, {G{\'a}bor N.} and Endre Szemer{\'e}di",

year = "2001",

doi = "10.1017/s0963548301004849",

language = "English (US)",

volume = "10",

pages = "397--416",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "5",

}

TY - JOUR

T1 - Spanning Trees in Dense Graphs

AU - Komlós, János

AU - Sárközy, Gábor N.

AU - Szemerédi, Endre

PY - 2001

Y1 - 2001

N2 - In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n0 such that, if n ≥ n0, T is a tree of order n and maximum degree at most cn/log n, and G is a graph of order n and minimum degree at least (1/2 + δ)n, then T is a subgraph of G.

AB - In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n0 such that, if n ≥ n0, T is a tree of order n and maximum degree at most cn/log n, and G is a graph of order n and minimum degree at least (1/2 + δ)n, then T is a subgraph of G.

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

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

U2 - 10.1017/s0963548301004849

DO - 10.1017/s0963548301004849

M3 - Article

AN - SCOPUS:0442326405

VL - 10

SP - 397

EP - 416

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

IS - 5

ER -