Asymptotic Enumeration of Extensional Acyclic Digraphs

作者：Wagner Stephan^*

来源：Algorithmica, 2013, 66(4): 829-847.

DOI：10.1007/s00453-012-9725-4

• Extensional acyclic digraphs
• Essential acyclic digraphs
• Full sets
• Asymptotic enumeration
• Limit theorems

The enumeration of extensional acyclic digraphs, which have the property that the outneighbourhoods are pairwise distinct, was considered in a recent article of Policriti and Tomescu. Several asymptotic questions were left as open problems. In this article, we determine the asymptotic number of such digraphs and show that a number of distributional results can be carried over from ordinary acyclic digraphs. In particular, we consider the distribution of the number of sources, the number of arcs, the maximum rank and the number of vertices of maximum rank, thereby also proving some conjectures made by Policriti and Tomescu. Finally, we study a very similar class of acyclic digraphs and provide analogous distributional results.

• 出版日期2013-8