Seminar of Graph Theory - Robert Lukoťka (7.10.2021)
Thursday 7.10.2021 at 9:50, Lecture room M/213
Robert Lukoťka:
Circular flow number of Goldberg snarks
Abstract:
A circular nowhere-zero r-flow on a bridgeless graph G is an orientation of the edges and an assignment of real values from [1, r-1] to the edges in such a way that the sum of incoming values equals the sum of outgoing values for every vertex. The circular flow number of G is the infimum over all values $r$ such that $G$ admits a nowhere-zero $r$-flow. We prove that the circular flow number of Goldberg snark G_{2k+1} is 4+1/(k+1), proving a conjecture of Goedgebeur, Mattiolo, and Mazzuoccolo [J.~Goedgebeur, D.~Mattiolo, G.~Mazzuoccolo: \emph{Computational results and new bounds for the circular flow number of snarks}, Discrete Mathematics 343 (2020), 112026.].
Besides this, we discuss computational aspects of circular flows. We describe an efficient way how to reformulate the problem of determining the circular flow number as a mixed linear programing problem. We review computational results obtained by this approach.