2
$\begingroup$

Given some fixed number of nodes $n$, which we will number 1 to $n$ in order to tell them apart, how many different strongly connected graphs can be created? Multiple edges with the same starting and ending nodes should be considered redundant and not contribute to the total.

For example, if $n$ is 2, we can create only one strongly connected graph, (the 2-cycle.) But if $n$ is 3 then we can create 18 different graphs: 2 with 3 edges, 9 with 4 edges, all 6 with 5 edges and the complete 3-graph.

Is there a known general formula for computing this number for a given $n$?

$\endgroup$
2
$\begingroup$

This is A003030. Everything known about this sequence is listed there.

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