1
$\begingroup$

Can anyone tell me how to compute the number of possible directed graphs with no self loops, given $e$ edges. Count all possible isomorphic graphs as $1$.

For example with one edge, there is only one way (treat edge from 1 to 2 is same as edge from 2 to 1).

For the case of $2$ edges there are $4$ possible ways:

  1. {(1,2),(2,1)},
  2. {(1,2),(2,3)}
  3. {(1,2),(3,2)}
  4. {(1,2),(3,4)}.

In this case treat {(1,2),(2,1)}={(2,1),(1,2)} and {(1,2),(3,2)}={(2,1),(2,3)}. (If we proceed this way, we at most require $2\times e$ nodes for $e$ edges.)

$\endgroup$
1
$\begingroup$

I believe you forgot {(1,2),(1,3)}, which brings the total for $2$ edges up to $5$.

See http://oeis.org/A053418 "Number of unlabeled directed graphs with n arcs and no isolated vertices", which begins $1, 5, 17, 80, 365, 1981,\ldots$. Sadly, I don't know of an elegant way to compute it.

$\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.