Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we remove the orientation of the arcs, thus getting an undirected graph $G'$ with diameter $D'$. Obviously, $D' \leq D$. What else can be said about $D$ and $D'$?. In particular, what can be said about $D$ and $D'$ if we know that $G$ is regular, vertex-transitive, or a Cayley graph?

  • $\begingroup$ what does it mean stronlgy connected? $\endgroup$
    – user126154
    Jul 5, 2014 at 0:38

1 Answer 1


Some answers are in Babai's paper https://people.cs.uchicago.edu/~laci/papers/eulerian-soda06.pdf. In particular, you have a very good bound if $G$ is Cayley, a quite good bound if $G$ is vertex-transitive, and negative results if $G$ is only regular.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .