The asymptotic number of acyclic digraphs. I

E. A. Bender, L. B. Richmond, R. W. Robinson, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

14 Citations (Scopus)

Abstract

We obtain an asymptotic formula for A n,q, the number of digraphs with n labeled vertices, q edges and no cycles. The derivation consists of two separate parts. In the first we analyze the generating function for A n,q so as to obtain a central limit theorem for an associated probability distribution. In the second part we show combinatorially that A n,q is a smooth function of q. By combining these results, we obtain the desired asymptotic formula.

Original languageEnglish
Pages (from-to)15-22
Number of pages8
JournalCombinatorica
Volume6
Issue number1
DOIs
Publication statusPublished - Mar 1986
Externally publishedYes

Keywords

  • AMS (1980) subject classification: 05C30, 05C20

Cite this