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

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

2 views
Skip to first unread message

Jack Muller

unread,
Jan 15, 2020, 9:03:32β€―AM1/15/20
to
Harary in "The number of linear, directed, rooted, and connected graphs"
considers, among others, the cases of rooted undirected graphs and
unrooted directed graphs. 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 reference so far. 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 0s
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, let a rooted directed graph be 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