Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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, since I didn't get any answer there for a week.

share|cite|improve this question
There are results for random undirected graphs, e.g. I am not aware of results for directed graphs. – Sasho Nikolov Mar 16 '12 at 19:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.