Nonabelian flows in networks

Journal of Graph Theory, vol. 104, pp. 245–256

Abstract

Abstract In this work we consider a generalization of graph flows. A graph flow is, in its simplest formulation, a labelling of the directed edges with real numbers subject to various constraints. A common constraint is conservation in a vertex, meaning that the sum of the labels on the incoming edges of this vertex equals the sum of those on the outgoing edges. One easy fact is that if a flow is conserving in all but one vertex, then it is also conserving in the remaining one. In our generalization we do not label the edges with real numbers, but with elements from an arbitrary group, where this fact becomes false in general. As we will show, graphs with the property that conservation of a flow in all but one vertex implies conservation in all vertices are precisely the planar graphs.

Authors 1

1. Daniël van Gent corresponding Aachen Mathematisch Instituut

   Leiden University

   Affiliation as printed

   Mathematisch Instituut, Leiden University Leiden The Netherlands

   Mathematisch Instituut, Leiden University, Leiden, The Netherlands