1
$\begingroup$

I need to count the number of simple directed graphs, with n vertices, without isolated vertices. There is additional note in task saying that we assume that two graphs are different if there are two vertices which are connected in first but disconnected in the second.

This whole 'no isolated vertices' thing connected with the fact that we are talking about directed graphs makes it way more complicated than different cases I've found on the Internet.

Basically the only tip I've got from my teacher is to use inclusion–exclusion principle to eliminate isolation cases but I don't really know how to do that.

$\endgroup$
0
$\begingroup$

For the case of $n$ labeled nodes we find using PIE the closed form $$D_n= \sum_{p=0}^n {n\choose p} (-1)^p 4^{n-p\choose 2}.$$ This will produce $$0, 3, 54, 3861, 1028700, 1067510583, 4390552197234, \ldots$$ which points to OEIS A054545 where it appears we have a match.

For the unlabeled case observe that the number $F_n$ of non-isomorphic digraphs was computed at the following MSE link. We then obtain for the number of digraphs with no isolated nodes

$$D_n = F_n - F_{n-1}$$

which will produce

$$0, 2, 13, 202, 9390, 1531336, 880492496, 1792477159408,\ldots$$

again a match, this time with OEIS A053598.

More data concerning PIE. The nodes of the poset for use with PIE correspond to all subsets $P$ of vertices of the $n$ vertices and represent labeled digraphs where the vertices in $P$, plus possibly some other vertices, are isolated. The weight on the the digraphs specified by $P$ is $(-1)^{|P|}.$ This means the digraphs with no isolated vertices have weight one because they appear only in the node that corresponds to $P=\emptyset.$ Digraphs with a set $Q$ of isolated vertices where $|Q|\ge 1$ appear in all nodes $P\subseteq Q,$ for a total weight of

$$\sum_{P\subseteq Q} (-1)^{|P|} = \sum_{p=0}^{|Q|} {|Q|\choose p} (-1)^p = 0,$$

i.e. zero. The cardinality of the set of diagraphs corresponding to node $P$ is $4^{n-|P|\choose 2}.$ We now sum the weights over all digraphs, collecting the contributions from all nodes where they appear. We already know that this will assign weight one to those with no isolated vertices and zero otherwise, providing the desired count. There are ${n\choose p}$ sets $P$ of $p=|P|$ nodes and there are $4^{n-p\choose 2}$ digraphs at these nodes with weight $(-1)^p$, concluding the derivation of the formula using PIE. Note that the count is the same regardless of whether we iterate over all digraphs, collecting the weights from the nodes or over all nodes, collecting the weights of all digraphs.

$\endgroup$
2
  • $\begingroup$ Could you tell me how to find that formula using PIE? I can't figure it out. I know that all of the possible cases (including isolated vertices) equals $$4^{n \choose 2}.$$ $\endgroup$ – k1npatsu Mar 12 '18 at 23:57
  • $\begingroup$ Explanatory material added. $\endgroup$ – Marko Riedel Mar 13 '18 at 2:05

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.