Accession Number:

ADA151015

Title:

On Matchings and Hamiltonian Cycles in Random Graphs.

Descriptive Note:

Management sciences research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

• Bollobas,B.
• Frieze,A. M.

Report Date:

1983-12-01

Pagination or Media Count:

36.0

Abstract:

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.

Descriptors:

• *GRAPHS
• *MATCHING
• *HAMILTONIAN FUNCTIONS
• PROBABILITY
• CYCLES
• NUMBERS
• MARKOV PROCESSES
• INEQUALITIES

Subject Categories:

• Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE