Connectivity in graphs and digraphs : maximizing vertex-, edge- and arc-connectivity with an emphasis on local connectivity properties

Holtkamp, Andreas; Guo, Yubao

doi:999910311466

Connectivity in graphs and digraphs : maximizing vertex-, edge- and arc-connectivity with an emphasis on local connectivity properties = Zusammenhang in Graphen und Digraphen : Maximierung von Ecken-, Kanten- und Bogenzusammenhang mit besonderem Hinblick auf lokale Zusammenhangseigenschaften

Holtkamp, Andreas (Author)

2013

VerantwortlichkeitsangabeAndreas Holtkamp

ImpressumAachen : Shaker 2013

UmfangIX, 144 S. : graph. Darst.

ReiheBerichte aus der Mathematik

Zugl.: Aachen, Techn. Hochsch., Diss., 2013

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Guo, Yubao (Thesis advisor)

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