Oriented Diameter (1978)

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 K4 by subdividing the three edges incident to one vertex. For general d, Chvátal and Thomassen [CT] showed that the answer is between .5d2+d and 2d2+2d.

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 (Cn\cart Cm) are tight. In particular, if n <= m, then Cn\cart Cm is tight except when 1) n,m are both odd, 2) n=3 and m is even, 3) n=4 and m is odd, or 4) n=5 and m is divisible by 4.

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.

Index Page Glossary