Search code examples
mathdiscrete-mathematics

Maximum number of directed graph

Given set of N points, what is the maximum number of directed graphs can be created ? I'm having trouble with isomorphic problem.
Edit (1): Only directed simple, non-loop vertex graph, doesn't required to be connected
Edit (2): Any point in this set is treated equally to each other, so the main problem here is to calculate and subtract the number of isomorphic graphs created from different sets of edges.

Solution

  • Number of unlabeled directed graphs with n vertices is here (OEIS A000273)

    1, 1, 3, 16, 218, 9608, 1540944, 882033440, 1793359192848

    There is no closed formula, approximated value is number of labeled graphs divided by number of vertex permutations:

      2^(n*(n-1)) / n!