More on counting acyclic digraphs

Details More on counting acyclic digraphs More on counting acyclic digraphs

2008-04-15

arxiv.org/abs/0804.2496v1

Mathematics

Combinatorics

4 pages

Scientific paper

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 $(2^r-1)$-multidigraphs of order $n$. Asymptotics follows easily since the main formula is represented by a simple equation in terms of special generating functions.

Affiliated with

Also associated with

No associations

Rating

More on counting acyclic digraphs 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 More on counting acyclic digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and More on counting acyclic digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-606699