How many different graphs are with V vertex?
The graph should be: Directed, connected, with no selfloops and no "paralleledges" (namely the same startpoint and endpoint).
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.
How many graphs?
Moderator: Board moderators
Re: How many graphs?
Does this help?  http://www.research.att.com/~njas/seque ... +connected

 Learning poster
 Posts: 51
 Joined: Tue Sep 04, 2007 2:12 pm
 Location: Russia, Saratov
 Contact:
Re: How many graphs?
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
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
Re: How many graphs?
Probably he meant strong connectivity by that.maxdiver wrote:How could the directed graph be connected?
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.

 New poster
 Posts: 18
 Joined: Sun Jul 20, 2008 7:05 pm
Re: How many graphs?
Thanks mf and maxdiver, these links point me for what I was looking for.