Bounds for the minimum oriented diameter
Sascha Kurz, Martin Lätsch
Abstract
We consider the problem of determining an orientation with minimum diameter of a connected and bridgeless graph $G$. Fomin et~al.{} discovered the relation $MOD(G)\le 9\gamma\!(G)-5$ between the minimum oriented diameter and the size $\gamma\!(G)$ of a
minimum dominating set. We improve their upper bound to $MOD(G)\le 4\gamma\!(G)$
Full Text: PDF PostScript