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.

  • $\begingroup$ There are results for random undirected graphs, e.g. www.jstor.org/stable/1998567. I am not aware of results for directed graphs. $\endgroup$ – Sasho Nikolov Mar 16 '12 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.