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
Bibliographic Metadata
- TitleCircular flows on signed graphs / by Michael Schubert ; Adviser: Prof. Dr. Eckhard Steffen
- Translated titleZirkuläre Flüsse auf signierten Graphen
- Author
- Participants
- Published
- Description1 Online-Ressource (xii, 98 Seiten) : Diagramme
- Institutional NoteUniversität Paderborn, Dissertation, 2018
- AnnotationTag der Verteidigung: 25.05.2018
- Defended on2018-05-25
- LanguageEnglish ; German
- Document TypesDissertation (PhD)
- URN
- DOI
- Social MediaShare
- Reference
- IIIF
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
- The PDF-Document has been downloaded 43 times.