Discrete Mathematics & Theoretical Computer Science, Vol 14, No 1 (2012)

Font Size:  Small  Medium  Large

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