Kurz, Sascha and Laetsch, Martin - Bounds for the minimum oriented diameter

dmtcs:567 - Discrete Mathematics & Theoretical Computer Science, May 13, 2012, Vol. 14 no. 1
Bounds for the minimum oriented diameter

Authors: Kurz, Sascha and Laetsch, Martin

We consider the problem of determining an orientation with minimum diameter MOD(G) of a connected and bridge-less graph G. In 2001 Fomin et al. discovered the relation MOD(G) <= 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) <= 4 gamma(G).


Source : oai:HAL:hal-00990564v1
Volume: Vol. 14 no. 1
Section: Graph and Algorithms
Published on: May 13, 2012
Submitted on: September 15, 2010
Keywords: diameter,orientation,domination,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 34 times.
This article's PDF has been downloaded 104 times.