I am aware of the standard work on the number of distinct non-equivalent directed graphs of size n... but I have a slightly different notion that has a practical application, and which I would really appreciate some insight on.
Let me define a concept of 'rank'.
The singleton directed set is of rank 0.
If two directed sets, A & B, are of rank n and m, and there is a single link from one element of A to an element of B and no other connection, then the result is of rank max(m,n) + 1. Thus in particular the linear order of n elements is of rank n-1 (and the tree of depth p is of rank p).
If two directed sets, A & B, are of rank n and m, and there is a single link from one element of A to an element of B and a single link from one element of B to one element of A, then the result is of rank max(m,n) + 1.
Thus we include in Rank n+1 directed graphs are directed graphs that can be decomposed into two subgraphs of rank n, A & B, with one link from an element of A to one of B and one from B to A.
If three directed sets, A & B & C, are of rank n, m & p, and there is a single link from A to B, one from B to C, and one from C to A, then the resulting structure is of rank max(n, m, p) + 2.
[And here is the part that is perhaps unexpected]
If three directed sets, A & B & C, are of rank n, m & p, and there is one link from A to B, one from B to C, and one from C to A and one from A to C, then the resulting structure is of rank max(n, m, p) + 2.
Tedious but simple enumeration shows that all connected directed graphs of 3 nodes are of rank 1 or 2 based on these definitions.
The basic idea is that something is of rank n only if it is 'complicated enough'. Thus A < B, B > A, A > C, C > D, D < C, is really two subgraphs 1: A < B, B > A and 2: C > D, D < C arranged in a tree 1 > 2, and thus is of rank 2 despite having 4 elements.
Two questions.
How does this generalize to rank n, so that all directed graphs with less than n+1 nodes are classified as rank p for p <= n?
How many distinct rank n connected directed graphs are there? It seems there is 1 of rank 1, 2 of rank 2, but my gut feeling is that it explodes fast, even though
Any help would be very much appreciated - and apologies if it isn't clear.