Universität zu Köln

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

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