# About the diameter of a graph after removing orientation

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.

## 1 Answer

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$.

• Well, the oriented diameter should be $n-1$, isn't it? – Hebert Jul 5 '14 at 10:09
• yes, you're right, corrected – user126154 Jul 5 '14 at 21:00
• 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 – Gerhard Paseman Jul 5 '14 at 21:12
• 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. – Hebert Jul 6 '14 at 9:37