×

Counting strongly-connected, moderately sparse directed graphs. (English) Zbl 1270.05059

Summary: A sharp asymptotic formula for the number of strongly connected digraphs on \(n\) labelled vertices with \(m\) arcs, under the condition \(m-n \gg n^{2/3}\), \(m = O(n)\), is obtained; this provides a partial solution of a problem posed by E. M. Wright back in 1977 [Q. J. Math., Oxf. II. Ser. 28, 363–367 (1977; Zbl 0335.05121)]. This formula is a counterpart of a classic asymptotic formula, due to E. A. Bender et al. [Australas. J. Comb. 6, 119–124 (1992; Zbl 0771.05087)], 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 N. Wormald [J. Comb. Theory, Ser. B 93, No. 2, 127–172 (2005; Zbl 1057.05044)] we rederived the BCM formula by counting first 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.

MSC:

05C30 Enumeration in graph theory
05C40 Connectivity
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aronson, Maximum matchings in sparse random graphs: Karp-Sipser revisited, Random Struct Algorithms 12 pp 111– (1998) · Zbl 0998.05058 · doi:10.1002/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#
[2] Bagaev, Random graphs with degree of connectedness 2 (Russian), Diskret Analiz 22 pp 3– (1973)
[3] Bender, The asymptotic number of labeled graphs with given degree sequences, J Comb Theory Ser A 24 pp 296– (1978) · Zbl 0402.05042 · doi:10.1016/0097-3165(78)90059-6
[4] Bender, The asymptotic number of labelled connected graphs with a given number of vertices and edges, Random Struct Algorithms 1 pp 127– (1990) · Zbl 0745.05022 · doi:10.1002/rsa.3240010202
[5] Bender, The asymptotic number of labelled weakly-connected digraphs with a given number of vertices and edges, Aust J Combin 6 pp 119– (1992) · Zbl 0771.05087
[6] Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, Eur J Comb 1 pp 311– (1980) · Zbl 0457.05038 · doi:10.1016/S0195-6698(80)80030-8
[7] Bollobás, The evolution of random graphs, Trans Am Math Soc 286 pp 257– (1984) · Zbl 0579.05046 · doi:10.2307/1999405
[8] Bollobás, Random graphs (2001) · doi:10.1017/CBO9780511814068
[9] H. Daudé V. Ravelomanana Random 2-XORSAT at the satisfiability threshold 2008 12 23 · Zbl 1136.68518
[10] Erd&0151;s, On the evolution of random graphs, Publ Math Hungar Acad Sci 5 pp 17– (1960)
[11] Flajolet, Airy phenomena and analytic combinatorics of connected graphs (electronic), Electron J Combin 11 pp 00– (2004) · Zbl 1053.05064
[12] van der Hofstad, Counting connected graphs asymptotically, Eur J Combin 27 pp 1294– (2006) · Zbl 1103.05040 · doi:10.1016/j.ejc.2006.05.006
[13] Janson, The birth of the giant component, Random Struct Algorithms 4 pp 233– (1993) · Zbl 0795.05127 · doi:10.1002/rsa.3240040303
[14] Karp, The transitive closure of a random digraph, Random Struct Algorithms 1 pp 73– (1990) · Zbl 0712.68076 · doi:10.1002/rsa.3240010106
[15] Łuczak, Component behavior near the critical point of the random graph process, Random Struct Algorithms 1 pp 287– (1990) · Zbl 0745.05048 · doi:10.1002/rsa.3240010305
[16] Łuczak, On the number of sparse random graphs, Random Struct Algorithms 1 pp 171– (1990) · Zbl 0735.05048 · doi:10.1002/rsa.3240010203
[17] Łuczak, The structure of a random graph near the point of the phase transition, Trans Am Math Soc 341 pp 721– (1994) · doi:10.1090/S0002-9947-1994-1138950-5
[18] Łuczak, The critical behavior of random digraphs, Random Struct Algorithms 35 pp 271– (2009) · Zbl 1214.05157 · doi:10.1002/rsa.20283
[19] B. D. McKay Asymptotics for 0 - 1 matrices with prescribed line sums Enumeration and design D. M. Jackson S. A. Vanstone Acadimic Press Canada Toronto 1984 225 238
[20] McKay, Asymptotics for symmetric 0 - 1 matrices with prescribed row sums, Ars Combin 19A pp 15– (1985) · Zbl 0568.05032
[21] McKay, Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2), Combinatorica 11 pp 369– (1991) · Zbl 0742.05047 · doi:10.1007/BF01275671
[22] Perez-Gimenez, Asymptotic enumeration of strongly connected digraphs by vertices and edges, Random Struct Algorithms (this issue)
[23] Pittel, Asymptotic enumeration of sparse graphs with a minimum degree constraint, J Comb Theory Ser A 101 pp 249– (2003) · Zbl 1017.05051 · doi:10.1016/S0097-3165(02)00017-1
[24] Pittel, Counting connected graphs inside-out, J Comb Theory Ser B 93 pp 122– (2005) · Zbl 1057.05044 · doi:10.1016/j.jctb.2004.09.005
[25] Pittel, Corrigendum to: ”Counting connected graphs inside-out” [J Combin Theory Ser B 93 (2005), 127-172], J Combin Theory Ser B 98 pp 835– (2008) · Zbl 1178.05052 · doi:10.1016/j.jctb.2007.10.005
[26] Pittel, How frequently is a system of 2-linear Boolean equations solvable?, Electron J Comb 17 pp R92– (2010) · Zbl 1193.05147
[27] Stepanov, On some feautures of the structure of a random graph near a critical point, Theory Probab Its Appl 32 pp 573– (1988) · Zbl 0656.60021 · doi:10.1137/1132091
[28] Wright, The number of connected sparsely edged graphs, J Graph Theory 1 pp 317– (1977) · Zbl 0337.05119 · doi:10.1002/jgt.3190010407
[29] Wright, The number of connected sparsely edged graphs, III. Asymptotic results, J Graph Theory 4 pp 393– (1980) · Zbl 0416.05048 · doi:10.1002/jgt.3190040409
[30] Wright, Formulae for the number of sparsely-edged strong labelled digraphs, Quart J Math Oxford Ser (2) 28 pp 363– (1977) · Zbl 0335.05121 · doi:10.1093/qmath/28.3.363
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.