Strong K-Connectivity in Digraphs and Random Digraphs
HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB
Pagination or Media Count:
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.
- Statistics and Probability