Bounds for the minimum oriented diameter

We consider the problem of finding an orientation with minimum diameter of a connected bridgeless graph. Fomin et. al. discovered a relation between the minimum oriented diameter an the size of a minimal dominating set. We improve their upper bound.
Wir betrachten das Problem eine Orientierung eines ungerichteten Graphen mit minimalem Durchmesser zu finden. Fomin entdeckte einen Zusammenhang zwischen der kardinalität einer kleinsten dominierenden Menge und eben diesem minimalen orientierten Durchmesser. Wir verbessern die dort gefundene obere Schranke.

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS
  • frontdoor_exportcitavi

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Institutes:Mathematik
Author: Sascha Kurz, Martin Lätsch
Year of Completion:2008
SWD-Keyword:Dominanz; Graph; Orientierung <Mathematik>
Tag:Dominanz; Durchmesser; Orientierung
diameter; domination; orientation
Dewey Decimal Classification:510 Mathematik
MSC-Classification:05C12 Distance in graphs
05C69 Dominating sets, independent sets, cliques
URN:urn:nbn:de:bvb:703-opus-4262
Document Type:Preprint
Language:English
Date of Publication (online):15.04.2008