On Matchings and Hamiltonian Cycles in Random Graphs.

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 (k/2) 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1983
Accession Number
ADA151015

Entities

People

  • A. M. Frieze
  • B. Bollobas

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Binomials
  • Computer Science
  • Contracts
  • Data Science
  • Inequalities
  • Information Science
  • Markov Processes
  • Mathematics
  • Probability
  • Random Variables
  • Sequences
  • Statistical Analysis
  • Statistics
  • Stochastic Processes
  • Universities

Fields of Study

  • Education

Readers

  • Calculus or Mathematical Analysis
  • Life Cycle Cost Analysis
  • Mathematical Modeling and Probability Theory.