Accession Number:

ADA109034

Title:

Strong K-Connectivity in Digraphs and Random Digraphs

Descriptive Note:

Technical rept.

Corporate Author:

HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s):

Report Date:

1981-10-01

Pagination or Media Count:

31.0

Abstract:

This paper concerns an extension of the strong connectivity notion in directed graphs. A digraph D is k-strongly connected if, for each x,y vertices of D, there exist or k vertex disjoint paths from x to y and also or k vertex disjoint paths from y to x. A k-strong block of a digraph D is a maximal k-strongly connected subgraph of D. We show here how many results about the k- blocks in undirected graphs extend to k-strong blocks in digraphs. Separation lemma, overlapping of k-strong blocks, number of them. We prove, for example, that the maximum number of k-strong blocks for all k or 1 in any n-vertex graph is 2n-13. We also prove that two k-strong blocks cannot have more than k-1 vertices in common. We furthermore present results bounding the cardinality of the biggest k-strong block in random digraphs of the Dn,p model. This work generalizes previous work on random undirected graphs.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE