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$
7
  • $\begingroup$ 1, 4, 36, 752, 45960, 9133760. Not in OEIS. I'll post about bounds soon. $\endgroup$ Commented Jan 15, 2020 at 23:30
  • 1
    $\begingroup$ It looks like column k=4 in oeis.org/A329874 $\endgroup$ Commented May 10, 2022 at 12:17
  • 1
    $\begingroup$ @MaxAlekseyev That's curious. Why should colouring with 4 colours give the same counts as rooting at one vertex? $\endgroup$ Commented May 10, 2022 at 13:24
  • 2
    $\begingroup$ @MaxAlekseyev Umm, it is shifted by 1. Rooted version for 6 vertices matches 4-colour version for 5 vertices. And now I see it: Given a rooted digraph, remove the root and colour the remaining vertices according to whether they were adjacent to/from/both/neither the root. $\endgroup$ Commented May 10, 2022 at 13:33
  • 1
    $\begingroup$ @MaxAlekseyev See A353996. $\endgroup$ Commented May 13, 2022 at 14:31

1 Answer 1

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$
1
  • $\begingroup$ For $n=3$, by underlying undirected graph: empty 1, one edge 5, two edges 15, three edges 15, total 36. $\endgroup$ Commented Jan 17, 2020 at 0:52

Your Answer

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