Sascha Kurz ; Martin Laetsch - Bounds for the minimum oriented diameter

dmtcs:567 - Discrete Mathematics & Theoretical Computer Science, May 13, 2012, Vol. 14 no. 1 - https://doi.org/10.46298/dmtcs.567
Bounds for the minimum oriented diameterArticle

Authors: Sascha Kurz 1; Martin Laetsch 2

  • 1 Mathematisches Institut [Bayreuth]
  • 2 Zentrum für Angewandte Informatik [Köln]

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).

https://doi.org/10.46298/dmtcs.567
Source: HAL:hal-00990564v1
Volume: Vol. 14 no. 1
Section: Graph and Algorithms
Published on: May 13, 2012
Accepted on: June 9, 2015
Submitted on: September 15, 2010
Keywords: diameter,orientation,domination,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 361 times.
This article's PDF has been downloaded 568 times.