Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many loop-free, weakly-connected digraphs of n vertices are there whose vertices all have indegree 1?

Here are two examples of such digraphs with $n = 5$:

  • $v_1 \to \{v_2, v_3, v_4, v_5\}; \; v_5 \to v_1$
  • $v_1 \to v_2; \; v_2 \to v_3; \; v_3 \to v_4; \; v_4 \to v_5; \; v_5 \to v_1$

Is there a theorem or formula that describes the number of these digraphs that exist for $n$ vertices, up to isomorphism?


Update: A commenter asked for some background.

I'm writing a puzzle for a game which the player must solve. The player activates a series of beam emitter-receivers (BER) in various positions. Each BER can receive only one beam but can emit as many as it wants to the other BERs.

The puzzle is solved when every BER is receiving energy from some other BER. I'm curious about the number of combinations that are possible with an n-instance configuration of BERs, so I asked this question.

share|improve this question
    
Fixed the title that I failed to fill out completely. Whoops. –  John Feminella Dec 24 '11 at 17:31
2  
Sometimes knowing how you came to consider a question will give a clue as to where the answer might be found. How did you encounter this question? –  dfeuer Dec 24 '11 at 17:46
    
If all vertices are reachable from vertex v, there are two cases: either v has an incoming edge or it does not. If it does not, then it is unique, and if I'm not very much mistaken the graph will be a tree, and there are loads of theorems about trees. –  dfeuer Dec 24 '11 at 18:15
    
@dfeuer I updated the post with the background you asked for. –  John Feminella Dec 24 '11 at 19:44
1  
My advice is to calculate the answer for a few small values of $n$ and then look up the resulting sequence in the Online Encyclopedia of Integer Sequences. –  Gerry Myerson Dec 25 '11 at 1:51

1 Answer 1

I just realized that you asked for the number of graphs different up to isomorphism, i.e. for unlabeled vertices. The number given below is the number of different graphs with labeled vertices, i.e. counting isomorphic graphs with different vertex labels as distinct.


I basically counted these graphs in this answer. Since each vertex has indegree $1$, there must be $n$ edges. There can be at most one pair of vertices with edges going both ways, since otherwise the associated undirected graph would have at most $n-2$ edges and thus wouldn't be connected. If there is such a pair, we can regard it as a "$2$-cycle" and treat this as a special case of a cycle. If there is no such pair, the associated undirected graph is a connected graph of $n$ vertices with $n$ edges. As Rahul noted in a comment, this must be a single cycle with a (possibly trivial) tree rooted at each vertex of the cycle.

Now it only remains to determine the number of ways of associating a digraph with these undirected graphs. The direction of the edges in the trees is fixed, and there are two choices for the direction of the edges in the cycle. Thus, the number of directed graphs is just twice the number of undirected graphs,

$$(n-1)!\sum_{k=2}^n\frac{n^{n-k}}{(n-k)!}\;,$$

where you can check that the $k=2$ case comes out right by noting that there are $n^{n-2}$ trees on $n$ vertices and we can choose the two-way edge as one of $n-1$ edges in each of these trees.

share|improve this answer
    
I think you're overcounting the number of directed graphs. Reversing the direction of the cycle may not give you a new graph, for example if the original graph is just the cycle itself. –  Rahul Dec 25 '11 at 5:28
    
@Rahul: See the disclaimer at the beginning of the answer. This counts the number of graphs on labeled vertices; in that case reversing the cycle does produce a new graph. –  joriki Dec 25 '11 at 7:05
    
Sorry, I didn't notice that at all. My mistake. –  Rahul Dec 25 '11 at 16:52

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.