Groups | Search | Server Info | Login | Register

Groups > ucb.math > #167

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

Show all headers | View raw

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.

Back to ucb.math | Previous | 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 21:32 +0100

csiph-web