Degree Sequences of Random Graphs.

Abstract

A property is said to be satisfied by almost all graphs on n vertices if the fraction of the graphs that satisfy it goes to 1 as n goes to infinity. For almost all graphs on n vertices the smallest vertex-degree is n/2 - sq. rt. <(n log n)/2 > + o (sq. rt. n). More generally we estimate the values in the tails of the degree sequence.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1979
Accession Number
ADA079744

Entities

People

  • Gérard Cornuéjols

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Binomials
  • Inequalities
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Military Research
  • New York
  • Operations Research
  • Optimization
  • Probability
  • Probability Distributions
  • Random Variables
  • Real Variables
  • Sequences
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Plasma Physics / Magnetohydrodynamics