Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

  1. 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?

  2. 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.

share|improve this question
    
Is it clear that the concept of rank is well-defined? That is, if there are two different ways of breaking a directed set down into a collection of smaller sets, will both ways necessarily give you the same number for the rank of the original? –  Gerry Myerson Jun 20 '12 at 23:19
2  
I agree with Gerry that the definition isn't clear. For example, you say that a path of $n$ vertices has rank $n-1$. However, if you join two paths of $n$ vertices into a single path of $2n$ vertices, the rank should be $2n-1$ but your first rule says that it is $\max(n-1,n-1)+1 = n$. –  Brendan McKay Jun 21 '12 at 0:36
    
Thank you... most helpful... –  David Jun 21 '12 at 7:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.