Mathematics – Combinatorics
Scientific paper
2010-05-03
Mathematics
Combinatorics
32 pages
Scientific paper
A sharp asymptotic formula for the number of strongly connected digraphs on $n$ labelled vertices with $m$ arcs, under a condition $m-n\to\infty$, $m=O(n)$, is obtained; this solves a problem posed by Wright back in $1977$. Our formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on $n$ vertices with $m$ edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula via counting two-connected graphs among the graphs of minimum degree $2$, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly-connected digraphs with parameters $m$ and $n$ among all such digraphs with positive in/out-degrees.
No associations
LandOfFree
Counting strongly-connected, sparsely edged directed graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Counting strongly-connected, sparsely edged directed graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting strongly-connected, sparsely edged directed graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-658859