The complexity of the zero-sum 3-flows
A zero-sum k-flow for a graph G  is a vector in the null-space of the 0,1 0 , 1 -incidence matrix of G  such that its entries belong to {1,?,(k?1)} {  1 , ? ,  ( k ? 1 ) } . We show that it is NP-complete to determine whether a given (3,4) ( 3 , 4 ) -semiregular graph has a zero-sum 3-flow.
zero-sum flow nowhere-zero flow zero-sum conjecture combinatorial problems (2 3) ( 2 3 ) -semiregular graph (2 3 ) (2 3 ) ( 2 3 )