# 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.

# Descriptors:

# Subject Categories:

- Statistics and Probability