OJ Board

How many different graphs are with V vertex?

The graph should be: Directed, connected, with no self-loops and no "parallel-edges" (namely the same start-point and end-point).

I'm trying to solve this problem for a long long time...

I really would appreciate if someone can point me some hint.

PS: The problem was in a online contest, and I wasn't able to find it again.

Thanks in advance, John.

Does this help? - http://www.research.att.com/~njas/seque ... +connected

How could the directed graph be connected? I am not familiar with such a term (for example, is graph 1->2 connected or not? you can't go from 2 to 1)

I know the solution for undirected graphs (connected and without loops and parallel edges), it's described on my site (it's in Russian, but I hope Google translator is enough to get an idea):
http://translate.google.com/translate?h ... e0=&swap=1

maxdiver wrote:How could the directed graph be connected?

Probably he meant strong connectivity by that.

Another possible notion of connectivity in digraphs is weak connectivity - when for each pair of vertices u, v, there's either a path from u to v, or a path from v to u, or both.

Thanks mf and maxdiver, these links point me for what I was looking for.