2001-38: On a Conjecture of Loebl

DIMACS TR: 2001-38

On a Conjecture of Loebl

Authors: Yi Zhao

ABSTRACT
Martin Loebl conjectured that if in a graph $G$ on $n$ vertices at least half the vertices have degree at least $n/2$, then $G$ contains, as subgraphs, all trees with at most $n/2$ edges. We prove the conjecture for sufficient large $n$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-38.ps.gz

DIMACS Home Page