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.