Strong K-Connectivity in Digraphs and Random Digraphs
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-1)/3). 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 D(n,p) model. This work generalizes previous work on random undirected graphs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1981
- Accession Number
- ADA109034
Entities
People
- John Reif
- Paul G. Spirakis
Organizations
- Harvard University