Two-Dimensional Nowhere- Zero Flows on Graphs
Determining Two-Dimensional Flow Numbers for Complete and Cubic Graphs
A.V. Lusthof (TU Delft - Electrical Engineering, Mathematics and Computer Science)
D.C. Gijswijt – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
E. Lorist – Graduation committee member (TU Delft - Electrical Engineering, Mathematics and Computer Science)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
A nowhere-zero flow on a directed graph is a function that assigns a value to each edge such that each vertex has equal in- and outflow. This concept is generalized to d-dimensional nowhere-zero flows. The two-dimensional flow number of a graph is the smallest number r such that the graph has a two-dimensional nowhere-zero flow using only vectors with lengts between 1 and r-1.
In this paper, two-dimensional flow numbers are determined for several graphs. First, these are determined for all complete multipartite graphs. Second, flow triangulations are researched, and a flow triangulation is found for the Wagner graph. Furthermore, this research addresses the question whether a nice flow triangulation exists for all bipartite cubic graphs. Furthermore, optimization models are used to approximate two-dimensional flow numbers of certain graphs, including snarks.