2
$\begingroup$

Given $|V|=4$ and $|E|=3$, how many distinct directed acyclic graphs can be formed? Isomorphic graphs should be counted as one.

  1. There is one where three periphery nodes point to a central node.
  2. There is a central node pointing to three periphery nodes.
  3. There are two variants of these two classes: one where two edges point out, and another where two edges point in.
  4. There is a linear graph $A\to B\to C\to D$.

Is these 5 classes all? How to solve this problem for a general graph? Incorporating acyclic property seems tough.

$\endgroup$
3
  • 1
    $\begingroup$ Haven't you missed $A \to B \leftarrow C \to D$? $A \leftarrow B \leftarrow C \to D$? $\endgroup$ – Stefan4024 Jun 21 '16 at 17:42
  • $\begingroup$ And indeed $A\to B\to C\leftarrow D$ $\endgroup$ – almagest Jun 21 '16 at 18:29
  • $\begingroup$ Are you not also missing a transitive triangle with an isolated vertex? $\endgroup$ – Shagnik Jun 22 '16 at 6:03
1
$\begingroup$

There are 9 such graphs.

First fix the isomorphism type of the underlying undirected graph. This can be a star, or a triangle and an isolated vertex, or a path.

Counting up to isomorphism, in the first case, there are 4 acylic orientations; in the second, just one, and in the third, again 4 orientations.

Also see number of directed acyclic graphs and a link there to count the number of acyclic orientations of a given undirected graph.

$\endgroup$

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.