DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
On Matchings and Hamiltonian Cycles in Random Graphs.
Management sciences research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
This document describes matchings and Hamiltonian cycles in random graphs. It is also shown that if a random graph G with vertices 1,2,...,n is constructed by randomly adding edges one at a time then, almost surely, as soon as G has degree k, G has k2 disjoint hamiltonian cycles plus a disjoint perfect matching if k is odd, where k is a fixed positive integer. Additional keywords Probability, Markov processes, and Inequalities.
APPROVED FOR PUBLIC RELEASE