Number of directed multigraphs with $n$ arrows

combinatoricsgraph theory

For context, I'm trying to work out the combinatorial properties of constructing a directed multigraph from a fixed number of arrows (with a vertex only existing when an arrow is connected to it).

How many possible directed multigraphs are there (up to isomorphism), given the following conditions?

  • There are a set number of edges.
  • There are no isolated vertices.
  • Edges and vertices are unlabelled.
  • There can be loops; that is, edges like $(a,a)$ are allowed in addition to $(a,b)$.
  • There can be multiple edges; that is, there can be more than one edge going from $a$ to $b$.

Another way to think about it is, how many isomorphism classes of multisets (with cardinality $n$) of ordered pairs (of, you could say, vertices) are there?

Best Answer

The case where vertices are labeled would be easy to count. The tool that lets us go from labeled to unlabeled vertices is the Pólya enumeration theorem. (The Wikipedia article gives an example of using this to count undirected graphs with a fixed number of edges, and the directed case is only slightly different.)

I will forget about isolated vertices for now, and allow directed edges $vw$ and $wv$ to coexist. So let's start with the complete directed graph (with $n$ vertices and all $N := n(n-1)$ possible directed edges), and color the edges with two colors: a color that represents "there is an edge" (with weight $1$) and a color that represents "there is no edge" (with weight $0$). The generating function of the set of colors is $f(t) = 1+t$. The weight of a coloring is the total weight of the colors used, so it's the number of edges in our graph; therefore, we want to find the number of colorings with a fixed weight.

We take $G$ to be the group $S_n$ acting on the vertices of the complete directed graph. To apply the Pólya enumeration theorem as in the Wikipedia article, we need to compute $Z_G(t_1, t_2, \dots, t_N)$. So, for each permutation $\sigma$ of the vertices and each $k \in \{1, \dots, N\}$, we need to compute $c_k(\sigma)$, the number of $k$-cycles in the action of $\sigma$ on the set of edges.

For example, let's try this for $n=3$ vertices, with $N = 6$ possible edges. Here, there are $3$ types of permutations:

  • The identity permutation fixes all edges, giving a $t_1^6$ term.
  • A swap like $(1\;2)$ acts on the set of edges by three $2$-cycles; the edges $12$ and $21$ are swapped, the edges $13$ and $23$ are swapped; the edges $31$ and $32$ are swapped. This gives a $t_2^3$ term, and there are three such permutations.
  • A permutation like $(1\;2\;3)$ acts on the set of edges by two $3$-cycles; the edges $12, 23, 31$ are permuted cyclically, and so are the edges $21, 32, 13$. This gives a $t_3^2$ term, and there are two such permutations.

So we get $Z_G(t_1, t_2, t_3, t_4, t_5, t_6) = \frac16(t_1^6 + 3 t_2^3 + 2 t_3^2).$ We might as well make this $Z_G(t_1, t_2, t_3)$ since no longer cycles appear.

By the Pólya enumeration theorem, the generating function of directed graphs on $3$ vertices up to isomorphism is \begin{align} Z_G(1 + t, 1 + t^2, 1 + t^3) &= \frac16((1+t)^6 + 3(1+t^2)^3 + 2(1+t^3)^2) \\ &= 1 + t + 4 t^2 + 4 t^3 + 4 t^4 + t^5 + t^6 \end{align} so there are $1, 1, 4, 4, 4, 1, 1$ directed graphs on $3$ vertices with $0, 1, 2, 3, 4, 5, 6$ edges respectively. Here is a diagram of all these graphs to verify the count:

enter image description here

You also wanted to rule out isolated vertices, which this doesn't do, but that's easy to fix. Let's say that $a_{n,m}$ is the number of $n$-vertex $m$-edge digraphs without the isolated vertex condition, and $a_{n,m}^*$ is the number that have no isolated vertices. Then we have $$ a_{n,m} = a_{0,m}^* + a_{1,m}^* + a_{2,m}^* + \dots + a_{n,m}^* $$ because the number of $n$-vertex $m$-edge digraphs with $k$ isolated vertices is counted by $a_{n-k,m}^*$. From this, we can get $a_{n,m}^* = a_{n,m} - a_{n-1,m}$.

Related Question