2
$\begingroup$

This question was posted a few days ago on the Mathematics StackExchange, but so far it has not been answered. 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? Thx.

$\endgroup$
2
$\begingroup$

Let $P$ be a polygon with $n$ edges, oriented clockwise. Now choose a point $x$ and add direct edges to all other points. Call this oriented graph $G$. Then the oriented diameter of $G$ is $n-1$ while the unoriented diameter is $2$.

$\endgroup$
4
  • 1
    $\begingroup$ Well, the oriented diameter should be $n-1$, isn't it? $\endgroup$ – Hebert Jul 5 '14 at 10:09
  • $\begingroup$ yes, you're right, corrected $\endgroup$ – user126154 Jul 5 '14 at 21:00
  • 1
    $\begingroup$ A similar construction on n ordered points (all edges decreasing except for (i,i+1) ) gives a directed path from 1 to n of length n-1, with the unoriented version being a complete graph of diameter 1. Gerhard "Likes One Downing The Competition" Paseman, 2014.07.05 $\endgroup$ – Gerhard Paseman Jul 5 '14 at 21:12
  • $\begingroup$ Thanks a lot Gerhard. I was just thinking about that construction too. These constructions are very useful examples. However, they are not even regular, let alone vertex-transitive. My impression is that in a vertex-transitive graph these extremal situations cannot occur. I would like to confirm or reject that. $\endgroup$ – Hebert Jul 6 '14 at 9:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.