K-Connectivity in Random Undirected Graphs.

Abstract

This paper concerns vertex connectivity in random graphs. We present results bounding the cardinality of the biggest k-block in random graphs of the G sub n,p model, for any constant value of k. These results generalize those of (Erdos, Renyi, 60) and (Karp, Tarjan, 80) for k = 1 and 2. We furthermore prove here that the cardinality of the biggest k-block is > or = n-logn with probability > or = 1/n-squared for p > or = c1(k)/n and c1(k) > k + 2. We also show that if p > or = c(k)(logn)/n with c(k) > 32 k-squared then the graph G sub n,p is k-connected with probability > or = 1-2n to the -d'(k) power, d'(k) > 1.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1981
Accession Number
ADA108826

Entities

People

  • John Reif
  • Paul G. Spirakis

Organizations

  • Harvard University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Classification
  • Computations
  • Construction
  • Distribution Functions
  • Mathematical Analysis
  • Mathematics
  • Military Research
  • Probability
  • Random Variables
  • Reliability
  • Security
  • Taxonomy
  • Universities
  • Vulnerability

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.