Groups | Search | Server Info | Login | Register

Groups > ucb.class.math1a > #1

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 
expression for an 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.class.math1a | 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:24 +0100

csiph-web