DIMACS TR: 96-58

On Perfect Matchings and Hamiltonian Cycles in Sums of Random Trees



Authors: Alan Frieze, Michal Karonski, and Lubos Thoma

ABSTRACT

We prove that the sum of two random trees almost surely possesses a perfect matching and the sum of five random trees almost surely possesses a Hamiltonian cycle.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-58.ps.gz
DIMACS Home Page