2013
Zugl.: Aachen, Techn. Hochsch., Diss., 2013
Genehmigende Fakultät
Fak01
Hauptberichter/Gutachter
Tag der mündlichen Prüfung/Habilitation
2013-05-29
Online
URN: urn:nbn:de:hbz:82-opus-47037
URL: https://publications.rwth-aachen.de/record/229924/files/4703.pdf
Einrichtungen
Inhaltliche Beschreibung (Schlagwörter)
Graphentheorie (Genormte SW) ; Lokaler Zusammenhang (Genormte SW) ; Mathematik (frei) ; Zusammenhang (frei) ; graph theory (frei) ; connectivity (frei) ; local connectivity (frei)
Thematische Einordnung (Klassifikation)
DDC: 510
msc: 05C40
Kurzfassung
Diese Dissertation präsentiert neue Ergebnisse und Ideen zum Zusammenhang von Graphen und Digraphen in besonderem Hinblick auf lokale Zusammenhangseigenschaften. Die Nachforschungen sind unterteilt in zwei Teile, einem ersten Teil über Graphen und einem Zweiten über Digraphen. Teil I behandelt einige wichtige Zusammenhangsparameter in Graphen - den Ecken-, Kanten- und eingeschränkten Kantenzusammenhang. Außerdem stellen wir eine lokale Version des eingeschränkten Kantenzusammenhangs vor. Wir präsentieren neue Ergebnisse zu allen genannten Parametern um (lokale) Maximalität/Optimalität in diversen Graphenklassen sicher zu stellen. In Teil II diskutieren wir Zusammenhangsparameter in Digraphen. Dies beinhaltet den maximalen lokalen Eckenzusammenhang regulärer und quasi-regulärer bipartiter Turniere, sowie den Eckenzusammenhang in lokalen Turnieren. Darüber hinaus studieren wir den eingeschränkten Bogenzusammenhang und ein dazu gehöriges Optimalitätskriterium von Turnieren und bipartite Turnieren. In Ergänzung stellen wir das Decycling-Problem für bipartite Turniere vor. Hierbei ist die minimale Anzahl an Bogen zu bestimmen, deren Entfernen in einem beliebigen bipartiten Turnier Kreisfreiheit sicherstellt. Zu guter letzt diskutieren wir ein lokales Optimalitätskriterium für maximale Netzwerkflüsse. Wir präsentieren ein allgemeines Verfahren um einen (eindeutigen) lokal optimalen maximalen Netzwerkfluss in einem beliebigen Netzwerk zu erhalten.This thesis presents new results and ideas on connectivity in graphs and digraphs with a special emphasis on local connectivity properties. The research is divided into two parts, the first part dealing with graphs and the second one with digraphs. In Part I of this thesis we study some important connectivity parameters for graphs such as the vertex-, edge- and restricted edge-connectivity. Also, we introduce a local version of the restricted edge-connectivity. We present new results for all of these parameters to ensure (local) maximality/optimality in various classes of graphs. In Part II of this thesis we discuss connectivity parameters for digraphs. This includes the maximal local vertex-connectivity of regular and almost regular bipartite tournaments, and the vertex-connectivity of local tournaments. Furthermore, we study the restricted arc-connectivity and an according optimality criteria for tournaments and bipartite tournaments. In addition, we make a short excursion to examine the decycling problem for bipartite tournaments, i.e. determining the minimum number of arcs to be deleted from an arbitrary bipartite tournament to attain acyclicity. Finally, we study local optimality criteria for maximum network flows. We introduce a general concept to obtain (unique) locally optimal maximum network flows for arbitrary networks.
Fulltext:
PDF
Dokumenttyp
Dissertation / PhD Thesis
Format
online, print
Sprache
English
Interne Identnummern
RWTH-CONV-144773
Datensatz-ID: 229924
Beteiligte Länder
Germany