Details

Autor(en) / Beteiligte

• Schubert, Michael
• Steffen, Eckhard[Akademischer Betreuer]

Titel

Circular flows on signed graphs : = Zirkuläre Flüsse auf signierten Graphen

Ort / Verlag

Paderborn

Erscheinungsjahr

2018

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 25.05.2018
• ger: In dieser Arbeit beschäftigen wir uns mit ganzzahligen und zirkulären nirgends-null Flüssen auf signierten Graphen, welche das Konzept von Färbungen verallgemeinern und verfeinern. Wir betrachten die Beziehung zwischen der zirkulären und der ganzzahligen Flusszahl eines signierten Graphen. Für Graphen, die einen nirgends-null Fluss zulassen, wurde die Vermutung aufgestellt, dass die Differenz zwischen ganzzahliger und zirkulärer Flusszahl kleiner als 1 ist. Wir widerlegen diese Vermutung, indem wir zeigen, dass die Differenz beliebig nahe bei 2 liegt. Wir stellen einige hinreichende Bedingungen für die Gleichheit der ganzzahligen und der aufgerundeten zirkulären Flusszahl auf. Das zirkuläre bzw. ganzzahlige Flussspektrum eines Graphen ist die Menge aller möglichen zirkulären bzw. ganzzahligen Flusszahlen, die durch beliebige zulässige Signaturen gegeben sind. Wir untersuchen Flussspektren von regulären Graphen und charakterisieren (2t+1)-reguläre Graphen, deren Flussspektrum 2+1/t enthält. Des Weiteren untersuchen wir Flussspektren von Graphen, die einen 1-Faktor besitzen. Mithilfe des entwickelten Konzepts von r-minimalen Mengen charakterisieren wir Graphen, die einen 1-Faktor besitzen. Wir finden kubische Graphen, deren ganzzahliges Flussspektrum nicht 5 oder 6 enthält und wir konstruieren eine unendliche Familie von brückenlosen kubischen Graphen mit ganzzahligem Flussspektrum {3,4,6}. Wir beweisen scharfe Schranken für die Kardinalität von kleinsten 3-minimalen und 4-minimalen Mengen. Wir beweisen Bouchets Vermutung für Kotzig Graphen. Wir untersuchen die Menge der zirkulären Flusszahlen, die durch reguläre signierte Graphen erhalten werden können. Abschließend charakterisieren wir signierte Graphen, die einen nirgends-null r-Fluss zulassen durch Orientierungen mit speziellen Eigenschaften.
• eng: In this thesis we study integer and circular nowhere-zero flows on signed graphs which generalize and refine the concept of colorings. We study the relation between the circular flow number and the integer flow number of a signed graph which are defined as the infimum over all r such that the given graph admits a circular nowhere-zero r-flow or an integer nowhere-zero r-flow, respectively. For flow-admissible graphs, it has been conjectured that the difference between the integer and the circular flow number is strictly smaller than 1. We disprove this conjecture by showing that the difference can be arbitrarily close to 2. We show some sufficient conditions for the equality of the integer flow number and the ceiling of the circular flow number. The circular or integer flow spectrum of a graph is the set of all possible circular or integer flow numbers given due to arbitrary flow-admissible signatures. We study integer and circular flow spectra on regular graphs. We characterize (2t+1)-regular graphs whose flow spectrum contains 2+1/t. Furthermore, we analyze some cases for the flow spectrum of a graph that has a 1-factor. By introducing the concept of r-minimal sets we characterize graphs that have a 1-factor. We find cubic graphs whose integer flow spectrum does not contain 5 or 6, and we construct an infinite family of bridgeless cubic graphs with integer flow spectrum {3,4,6}. We prove some sharp bounds for the cardinality of smallest 3-minimal and 4-minimal sets, respectively. We prove that Bouchet's conjecture is true for Kotzig-graphs. We study the set of circular flow numbers that can be obtained by regular signed graphs and entirely determine the set of flow numbers for regular unsigned graphs up to 5, which is best possible if Tutte's 5-flow conjecture is true. We characterize signed graphs that admit a circular nowhere-zero r-flow by finding orientations...