Explicit upper bound on the number of simple rooted directed graphs on 𝑛 vertices?

Question

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.

Answer 1

1, 4, 36, 752, 45960, 9133760, 6154473664

Let $a(n)$ be the number you want. If all of the digraphs had a trivial automorphism group, then the number of them would be $$ \ell(n) = \frac{4^{\binom n2}}{(n-1)!}. $$

This is an exact lower bound: $\ell(n)\le a(n)$. Now it is a fact that most digraphs have a trivial automorphism group, in fact all but a exponentially small fraction as $n\to\infty$. So we have $a(n)\sim\ell(n)$ and for any constant $c>1$, $a(n)\le c\ell( n)$ if $n$ is large enough. This much is easy to prove. It would be somewhat harder to make "large enough" into an explicit statement.

Looking at the first 7 ratios $a(n)/\ell(n)$ shows the convergence is rapid: $$1.0000, 1.0000, 1.1250, 1.1016, 1.0519, 1.0208, 1.0075$$ A safe conjecture is that these ratios are decreasing for $n\ge 3$ and the largest value is $\frac 98$. But I don't have a proof.