Spanning Trees in Dense Graphs

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

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)397-416
Number of pages20
JournalCombinatorics Probability and Computing
Volume10
Issue number5
DOIs
StatePublished - 2001

All Science Journal Classification (ASJC) codes

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

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

Cite this