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$

1 Answer 1

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, 2014 at 10:09
  • $\begingroup$ yes, you're right, corrected $\endgroup$
    – user126154
    Jul 5, 2014 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$ Jul 5, 2014 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, 2014 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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