Jack Muller
unread,Jan 15, 2020, 3:32:22β―PM1/15/20You do not have permission to delete messages in this group
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
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.