Jack Muller
unread,Jan 15, 2020, 9:03:32β―AM1/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 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.