RESOLUTION OF IRREDUCIBLE INTEGRAL FLOWS ON A SIGNED

Abstract. We completely describe the structure of irreducible integral flows on a signed graph by lifting them to the signed double covering graph. A (real-valued) flow (sometimes also called a circulation) on a graph or a signed graph (a graph with signed edges) is a real-valued function on oriented edges, f: � E → R, such that the net inflow to any vertex is zero. An integral flow is a flow whose values are integers. There are many reasons to be interested in flows on graphs; an important one is their relationship to graph structure through the analysis of irreducible flows, that is, integral flows that cannot be decomposed as the sum of other flows of lesser value. It is well known, and an important observation in the thoery of integral network flows, that the irreducible flows are identical to the circuit flows, which have value 1 on the edges of a graph circuit (that is, a cycle) and 0 on all other edges. Extending the theory of irreducible integral flows to signed graphs, which was one of the topics of the doctoral dissertation of Wang [4], led to the remarkable discovery that there are, besides the anticipated circuit flows (which in signed graphs are already more complicated than in unsigned graphs), also many ‘strange ’ irreducible flows with elaborate structure not describable by circuits. In this article we characterize that structure by liftin