Lätsch, Martin (2008). Schranken für den minimalen orientierten Durchmesser. PhD thesis, Universität zu Köln.

[thumbnail of dissertation_martin_laetsch.pdf]
Preview
 PDF
dissertation_martin_laetsch.pdf
Download (722kB)

Abstract

Wir betrachten in dieser Arbeit das Problem, die Kanten eines Graphen so zu orientieren, dass der Durchmesser des gerichteten Graphen minimal ist. Wir geben eine Schranke für den minimalen orientierten Durchmesser in Abhängigkeit der Kardinalität einer kleinsten dominierenden Menge an. Weiter zeigen wir, wie bei gegebener dominierender Menge eine Orientierung eines Graphen konstruiert werden kann, so dass der Durchmesser der Orientierung kleiner gleich dem Vierfachen der Kardinalität der dominierenden Menge ist. Für die Klasse der Graphen, die weder einen Kreis der Länge drei noch einen Kreis der Länge vier enthalten, zeigen wir eine scharfe Schranke für den minimalen orientierten Durchmesser in Abhängigkeit der Dominanzzahl. In einem weiteren Kapitel betrachten wir bigerichtete Graphen. Wir charakterisieren die Klasse der bigerichteten Graphen, für die eine stark zusammenhängende bigerichtete Orientierung existiert und geben eine Schranke für den minimalen bigerichteten Durchmesser in Abhängigkeit der Kardinalität einer kleinsten dominierenden Menge an.

Item Type: Thesis (PhD thesis)
Translated title:
Title
Language
Bounds for the minimum oriented diameter
English
Translated abstract:
Abstract
Language
In this thesis, we consider the problem of finding an orientation of an undirected graph with minimal diameter. We show a relation between the minimum oriented diameter of an undirected graph and the size of a minimal dominating set. Furthermore, if we have a graph and a dominating set, not necessarily a minimal dominating set, we show how to construct an orientation in polynomial time, such that the diameter of the orientation is less or equal to four times the size of the dominating set. Furthermore, we determine the exact upper bound for graphs without cycles of length three and four. We consider bidirected graphs and characterize undirected graphs that allow a strongly connected bidirection. For those graphs we show an upper bound for the bidirected diameter, which depends on the size of a minimal dominating set.
English
Creators:
Creators
Email
ORCID
ORCID Put Code
Lätsch, Martin
laetsch@zpr.uni-koeln.de
UNSPECIFIED
UNSPECIFIED
URN: urn:nbn:de:hbz:38-25102
Date: 2008
Language: German
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Mathematical Institute
Subjects: Mathematics
Uncontrolled Keywords:
Keywords
Language
Digraph, orientierter Durchmesser, Dominanzzahl, bigerichteter Graph
German
Digraph, oriented diameter, dominating set, bidirected graph
English
Date of oral exam: 16 October 2008
Referee:
Name
Academic Title
Schrader, Rainer
Prof. Dr.
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/2510

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item