2
$\begingroup$

If all the number of all the possible DAGs are K, then K can consist of

  • disconnected vertices (not all connected vertices)
  • from the directionality of a particular edge is counted as a new graph

My attempt to analyze: Example for 2 nodes X,Y ;

  1. G1 : {X,Y} ( all disconnected)
  2. G2 : {X->Y}
  3. G3 : {X<-Y} ( directionality changes)

But for 3 nodes X, Y, Z; there are a large number of possible graphs;

  1. set 1: with 1 edge
  2. set 2: with 2 edges
  3. set 3: with 3 edges
  4. set 4: with 0 edges

Likewise, the possible space is growing.

I tried, this resource but when I try to cont it for 2 edges it should be (2^(2^2)), but it violates my above analysis. Maybe this solution is not applicable to my situation.

May I know any clue on how to count the number of all the possible DAGs that can be generated using N vertices incorporating the above analysis?

$\endgroup$
1
$\begingroup$

This is OEIS A003024. The entry has number of references, an asymptotic approximation, and the recurrence

$$a_n=\sum_{k=1}^n(-1)^{k+1}\binom{n}k2^{k(n-k)}a_{n-k}$$

with $a_0=1$, but no closed form, so it seems likely that no closed form is known.

$\endgroup$
4
  • $\begingroup$ I see, Thank you for helping! I I was wondering how to derive this, hence I tried to find the resource R. W. Robinson, Counting labeled acyclic digraphs., but I could not find an accessible resource. I would appreciate it if could suggest any accessible resource on this? Meanwhile, I found this paper which cites the same resource, but it mentioned the recurrence in a different way. So, I'm really interested in the derivation of this equation. $\endgroup$ – Sachz Oct 18 '20 at 23:25
  • 1
    $\begingroup$ @SachzEMSPE: If I’m not mistaken, it can be derived from Theorem $1$ of the paper by Rodionov noted in the OEIS entry. $\endgroup$ – Brian M. Scott Oct 18 '20 at 23:33
  • 1
    $\begingroup$ Thank you for the resource! It is accessible. Let me give it a try. $\endgroup$ – Sachz Oct 18 '20 at 23:44
  • $\begingroup$ @SachzEMSPE: You’re welcome! $\endgroup$ – Brian M. Scott Oct 18 '20 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.