I would like to know if there is any known relation between diameter and density in (connected) simple digraphs. Asymptotic results for nāā, statistical, conditioned results that would restrict the graph class to a subset of all digraphs are also welcome...
For example, let's say I have a digraph $G$ constructed by the following algorithm :
- produce $n$ vertices : $V_{G} = \{v_{i}, 0 < i < n\}$
- for each vertex $v_{i}$, create the edge $i \rightarrow j$ with probability $p$
Let $G_{2}$ be the biggest strongly subgraph of $G$. Can we deduce a statistical relationship between the diameter $D(G_{2})$ and $p$ ?
EDIT : No answer seems to come, so any possible answer related to graphs that are defined through a different process (different random process, fixed arity, characterized subset of digraphs...) is also plainly welcome !
The goal is to use that relation in a complexity analysis, where the estimated complexity in time of an algorithm $A$ on a strongly connected digraph $G$ is $C(A,G) = D(G) * |V_{G}| * |E_{G}|$, where $D(G)$ is the diameter of $G$. I'd like to reduce the expression of mean complexity to an expression of $|V_{G}|$ and $|E_{G}|$ only.
Thanks by advance, Alex
PS : I ported this question from math.stackexchange.com, since I didn't get any answer there for a week.