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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.