TY - JOUR

T1 - On the existence of an integral potential in a weighted bidirected graph

AU - Hurkens, C.A.J.

PY - 1989

Y1 - 1989

N2 - A. Schrijver proved that if A denotes the incidence matrix of a bidirected graph, and b is an integral "length" function on the edges of A, then the system Axb has an integer solution x if and only if (i) each cycle in A has nonnegative length, and (ii) each doubly odd cycle in A has positive length. Unfortunately these cycles may be very complicated. We show that we may restrict conditions (i) and (ii) to a set of reasonably simple cycles.

AB - A. Schrijver proved that if A denotes the incidence matrix of a bidirected graph, and b is an integral "length" function on the edges of A, then the system Axb has an integer solution x if and only if (i) each cycle in A has nonnegative length, and (ii) each doubly odd cycle in A has positive length. Unfortunately these cycles may be very complicated. We show that we may restrict conditions (i) and (ii) to a set of reasonably simple cycles.

U2 - 10.1016/0024-3795(89)90479-5

DO - 10.1016/0024-3795(89)90479-5

M3 - Article

VL - 114-115

SP - 541

EP - 553

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

ER -