Jack Muller
unread,Jan 15, 2020, 12:06:17β―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 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 literature 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, 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.