Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > tum.math.general > #2

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

Show all headers | View raw

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.

Back to tum.math.general | Previous | Next | Find similar | Unroll thread

Thread

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

csiph-web