1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 1, 4, 36, 752, 45960, 9133760. Not in OEIS. I'll post about bounds soon. $\endgroup$ – Brendan McKay Jan 15 '20 at 23:30
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For $n=3$, by underlying undirected graph: empty 1, one edge 5, two edges 15, three edges 15, total 36. $\endgroup$ – Brendan McKay Jan 17 '20 at 0:52

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy