Spanning Trees in Dense Graphs

JÁNOS KOMLÓS, GÁBOR N. SÁRKÓZY, ENDRE SZEMERÉDI

Source record

Source: Crossref

Published: Sep 1, 2001

DOI: 10.1017/s0963548301004849

Open original source ↗

Source abstract

In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n 0 such that, if n [ges ] n 0 , 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 .

Evidence graph

No public relationships recorded yet.

Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.