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.

  • $\begingroup$ Fixed the title that I failed to fill out completely. Whoops. $\endgroup$ Dec 24 '11 at 17:31
  • 2
    $\begingroup$ 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? $\endgroup$
    – dfeuer
    Dec 24 '11 at 17:46
  • $\begingroup$ 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. $\endgroup$
    – dfeuer
    Dec 24 '11 at 18:15
  • $\begingroup$ @dfeuer I updated the post with the background you asked for. $\endgroup$ Dec 24 '11 at 19:44
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 25 '11 at 1:51

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,


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.

  • $\begingroup$ 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. $\endgroup$
    – user856
    Dec 25 '11 at 5:28
  • $\begingroup$ @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. $\endgroup$
    – joriki
    Dec 25 '11 at 7:05
  • $\begingroup$ Sorry, I didn't notice that at all. My mistake. $\endgroup$
    – user856
    Dec 25 '11 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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