2008/04/15 by Valery A. Liskovets, Liskovets, Valery A. · 1 citation
Computer Science · Mathematics · #05C30 (Primary) #52B11 #57M15 (Secondary) #5A16 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Geometric Topology (math.GT) #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.0804.2496
openalex publication_date 2008/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note we derive enumerative formulas for several types of labelled acyclic directed graphs by slight modifications of the familiar recursive formula for simple acyclic digraphs. These considerations are motivated by, and based upon, recent combinatorial results in geometric topology obtained by S.Choi, who established exact correspondences between acyclic digraphs and so-called small covers over hypercubes and related polytopes. In particular, we show that the number of equivalence classes of small covers over the cartesian product of n copies of an r-simplex is equal to the number of acyclic (2r-1)-multidigraphs of order n. Asymptotics follows easily since the main formula is represented by a simple equation in terms of special generating functions.