We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Counting strongly connected (k<sub>1</sub>, k<sub>2</sub>)‐directed cores.
- Authors
Pittel, Boris
- Abstract
Consider the set of all digraphs on [ N ] with M edges, whose minimum in‐degree and minimum out‐degree are at least k1 and k2 respectively. For k : = min { k 1 , k 2 } ≥ 2 and M / N ≥ max { k 1 , k 2 } + ɛ , M = Θ ( N ), we show that, among those digraphs, the fraction of k‐strongly connected digraphs is 1 − O ( N − ( k − 1 ) ). Earlier with Dan Poole we identified a sharp edge‐density threshold c ∗ ( k 1 , k 2 ) for birth of a giant (k1, k2)‐core in the random digraph D ( n , m = [ c n ] ). Combining the claims, for c > c ∗ ( k 1 , k 2 ) with probability 1 − O ( N − ( k − 1 ) ) the giant (k1, k2)‐core exists and is k‐strongly connected.
- Subjects
GRAPH connectivity; DIRECTED graphs; PATHS &; cycles in graph theory; GRAPH theory; COMBINATORICS
- Publication
Random Structures & Algorithms, 2018, Vol 53, Issue 1, p3
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20759