Counting strongly connected (k₁,k₂)-directed cores

2016/09/01 by Boris Pittel, Pittel, Boris
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1609.00290

openalex publication_date 2016/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Consider the set of all digraphs on [N] with M edges, whose minimum in-degree and minimum out-degree are at least k₁ and k₂ respectively. For k:=min\k₁,k₂\≥ 2 and M/N>max\k₁,k₂\, 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₁,k₂) for birth of a giant (k₁,k₂)-core in the random digraph D(n,m=[cn]). Combining the claims, for c>c^*(k₁,k₂) with probability 1-O(N^-(k-1)) the giant (k₁,k₂)-core exists and is k-strongly connected.

Related

• Birth of a giant (k₁,k₂)-core in the random digraph
• The number of edges in critical strongly connected graphs
• A simple solution to the k-core problem
• Asymptotic enumeration of strongly connected digraphs by vertices and edges
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs