Groups | Search | Server Info | Login | Register

Groups > japan.sci.math > #10

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

Show all headers | View raw

Harary considers in "The number of linear, directed, rooted, and 
connected graphs" (among other problems) 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.

Back to japan.sci.math | Previous | Next | Find similar

Thread

Upper bound on the number of simple rooted directed graphs on 𝑛 vertices? Jack Muller <Just_A_ManFUCKSPAM@mein.SPAMFUCKgmx> - 2020-01-15 18:10 +0100

csiph-web