Harary mentioned this problem in "The number of linear, directed, rooted, and connected graphs" on p. 455, l. 3β5, but a short and crisp upper bound is missing. I believe that someone must have computed a good upper bound on the number of rooted directed graphs up to isomorphism, but I failed to find a literature reference. Could anyone help? In this question, we consider only simple graphs, which have no multiple edges or graph loops (corresponding to a binary adjacency matrix with zeroes on the diagonal). Two rooted directed graphs are considered the same iff there is a bijection between the vertices that induces an orientation-preserving bijection on the edges and sends the root of one graph to the root of the other.

Here is a formalization of the setup.

In the following, a *directed rooted graph* is a triple (π,πΈ,π) where π is a set, πΈβπΓπ, and πβπ. We call such a rooted directed graph *simple* iff βπ₯βπ:(π₯,π₯)βπΈ.

We call rooted directed graphs (π,πΈ,π) and (πΜ
,πΈΜ
,πΜ
) *isomorphic* iff there is a bijection π:πβͺπΜ
such that π(π)=πΜ
and πΈΜ
={(π(π₯),π(π₯β²))|(π₯,π₯β²)βπΈ}.

What would be a good and explicit closed-form upper bound on the maximal number of pairwise nonisomorphic rooted simple directed graphs on π vertices (πβββ)? (If my calculations by hand contain no errors, the first terms of the corresponding integer sequence are 1,4,36. I looked up "graph 1,4,36" in OEIS, but the only entry that appeared said nothing to me.)

Ideally, the upper bound should be elementary expressible using the operations (in this priority) exponentiation, factorial, multiplication, addition, binomial, multinomial, division, and subtraction.

Literature references are welcome.

2more comments