0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Jun 20, 2012 at 23:19
  • 2
    $\begingroup$ 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$. $\endgroup$ Jun 21, 2012 at 0:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.