6
$\begingroup$

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.

  • 0
    @joriki Can you enumerate how you got $9$ for $n = 5$? I must be missing one of the isomorphisms as I only got 8.2011-12-26

1 Answers 1

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.

  • 0
    Sorry, I didn't notice that at all. My mistake.2011-12-25