Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T12:23:45.247Z Has data issue: false hasContentIssue false
  • English
  • Français

Spanning Trees in Dense Graphs

Published online by Cambridge University Press:  12 December 2001

JÁNOS KOMLÓS ,
GÁBOR N. SÁRKÓZY  and
ENDRE SZEMERÉDI
JÁNOS KOMLÓS
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA
GÁBOR N. SÁRKÓZY
Affiliation:
Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA
ENDRE SZEMERÉDI
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA Hungarian Academy of Sciences, Budapest, Hungary
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 10 , Issue 5 , September 2001 , pp. 397 - 416
Copyright
2001 Cambridge University Press