Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

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

0 views
Skip to first unread message

Jack Muller

unread,
Jan 15, 2020, 3:32:22β€―PM1/15/20
to
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 the 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 closed-form upper bound on the maximal number of
pairwise nonisomorphic rooted simple directed graphs on 𝑛 vertices (π‘›βˆˆβ„•β‚Š)?

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

Literature references are welcome.
0 new messages