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; Guo, Yubao (Thesis advisor)

Aachen : Shaker (2013)
Doktorarbeit

In: Berichte aus der Mathematik
Seite(n)/Artikel-Nr.: IX, 144 S. : graph. Darst.

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

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.