Go to page
 

Bibliographic Metadata

Title
Circular flows on signed graphs / by Michael Schubert ; Adviser: Prof. Dr. Eckhard Steffen
Additional Titles
Zirkuläre Flüsse auf signierten Graphen
AuthorSchubert, Michael
ParticipantsSteffen, Eckhard
PublishedPaderborn, 2018
Edition
Elektronische Ressource
Description1 Online-Ressource (xii, 98 Seiten) : Diagramme
Institutional NoteUniversität Paderborn, Dissertation, 2018
Annotation
Tag der Verteidigung: 25.05.2018
Defended on2018-05-25
LanguageEnglish ; German
Document TypesDissertation (PhD)
URNurn:nbn:de:hbz:466:2-30824 
DOI10.17619/UNIPB/1-329 
Files
Circular flows on signed graphs [1.13 mb]
Links
Reference
Classification
Abstract (German)

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

Abstract (English)

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

License
CC-BY-License (4.0)Creative Commons Attribution 4.0 International License