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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$.
-
1$\begingroup$ Well, the oriented diameter should be $n-1$, isn't it? $\endgroup$– HebertCommented Jul 5, 2014 at 10:09
-
-
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$ Commented 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$– HebertCommented Jul 6, 2014 at 9:37