**Originator(s):**
Vasek Chvátal and Carsten Thomassen

**Definitions:**
The *diameter* of a strong digraph is the maximum of *d(x,y)* over
ordered vertex pairs *(x,y)*. The *oriented diameter* of an
(undirected) graph *G* is the smallest diameter among strong orientations
of *G*.

**Conjecture/Question:**
How large can the oriented diameter be for a graph of diameter *d*?

**Background/motivation:**
Robbins' Theorem [R] states that a graph *G* has a strongly connected
orientation if and only if *G* has no cut-edge. Such a question might
arise when making the streets of a city one-way or when building a
communication network with links that are reliable only in one direction.
The natural objective is to choose the orientations so that not only is the
resulting digraph strongly connected, but also it has a short *u,v*-path
for every ordered pair *u,v\in V(G)*.

**Comments/Partial results:**
For *d=2*, the answer is 6, achieved by the Petersen graph and by the
graph obtained from *K _{4}* by subdividing the three edges
incident to one vertex. For general

The oriented diameter is trivially at least the diameter. Graphs where
equality holds are said to be *tight*. McCanna [M] proved that
hypercubes with dimension at least four are tight.
König, Krumme, and Lazard [KKL] determined precisely which discrete tori
(*C _{n}\cart C_{m}*) are tight. In particular, if

**References:**

[CT] Chvátal, V.; Thomassen, C. Distances in orientations of graphs.
J. Combinatorial Theory Ser. B 24 (1978), no. 1, 61--75.

[KKL] König, J.-C.; Krumme, D. W.; Lazard, E.
Diameter-preserving orientations of the torus.
Networks 32 (1998), no. 1, 1--11.

[M] McCanna, J. E. Orientations of the *n*-cube with minimum diameter.
Discrete Math. 68 (1988), no. 2-3, 309--310.

[R] Robbins, H. E. A theorem on graphs, with an application to a problem
in traffic control. Amer. Math. Monthly 46 (1939), 281--283.