96-58: On Perfect Matchings and Hamiltonian Cycles in Sums of Random Trees

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