{'fraction_non_alphanumeric': 0.06756674014205241, 'fraction_numerical': 0.019991427871662994, 'mean_word_length': 3.0272469485883367, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 27, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On 1-sum flows in undirected graphs

Let G=(V,E) be a simple undirected graph. For a given set L of the real line, a function omega from E to L is called an L-flow. Given a vector gamma whose coordinates are indexed by V, we say that omega is a gamma-L-flow if for each v in V, the sum of the values on the edges incident to v is gamma(v). If gamma(v)=c, for all v in V, then the gamma-L-flow is called a c-sum L-flow. In this paper we study the existence of gamma-L-flows for various choices of sets L of real numbers, with an emphasis on 1-sum flows. Given a natural k number, a c-sum k-flow is a c-sum flow with values from the set {-1,1,...,1-k, k-1}. Let L be a subset of real numbers containing 0 and let L* be L minus 0 by L*. Answering a question from a recent paper we characterize which bipartite graphs admit a 1-sum R*-flow or a 1-sum Z*-flow. We also show that that every k-regular graph, with k either odd or congruent to 2 modulo 4, admits a 1-sum {-1, 0, 1}-flow.


Introduction
Let G = (V, E) be a simple undirected graph with n = |V | vertices and m = |E| edges. We say that a vertex v ∈ V and an edge e ∈ E are incident if e = {v, u}. Assign a weight ω : E → R. In this paper we view ω as a flow in G. The value of ω at v ∈ V , denoted as γ(v), is given by γ(v) = e∈E,v∈e ω(e). By abuse of notation we view ω = (ω(e)) e∈E , γ = (γ(v)) v∈V as column vectors in R E , R V , respectively. For a given set L ⊂ R, ω is called an L-flow if ω : E → L. Thus an R-flow is just a flow defined above. Given a vector γ ∈ R V we say that ω is a γ-L-flow if the value of an L-flow ω on each vertex v is γ(v). Let c ∈ R. Then γ-L-flow is called a c-sum L-flow if γ(v) = c for all v ∈ V and ω : E → L.
In this paper we study the existence problem of γ-L-flow on undirected graphs. The problem of finding c-sum S-flows was studied in the papers [2,3,1,4]. For simplicity of exposition we will assume that G is a connected graph.
The existence of γ-R-flow is a linear algebra problem. Let L ⊂ R be an interval. (It may be open, closed, half open, finite or infinite.) Then the existence of γ-L-flow is a problem linear programming related to graphs. See for example [8].
2 Existence of γ-interval-flows Given a value γ and an interval L the most basic is whether a graph G has a γ-L-flow or not. If L is the entire real line this a purely linear algebraic question, and when L is a proper subinterval of reals we can apply methods from linear programming to find conditions for its solvability. In this section we will first strengthen an existence result from [4] for γ-R-flows and then look at the case when L is a proper subinterval.

Existence of γ-R-flows
Let G = (V, E) be a simple undirected graph. Let A(G) := A = [a ve ] ∈ R V ×E be the vertex edge incidence matrix of G. That is a ve = 1 if v ∈ e and a ve = 0 otherwise. It is well known that A is unimodular, i.e. all its minors have values in the set {−1, 0, 1}, if and only if G is bipartite [10]. (See [8, §6.5] for a textbook reference.) Assume that G is connected. Then rank A = n if G contains an odd cycle and rank A = n − 1 if G is bipartite [9, p. 63]. The following result is a more detailed version of the result proved in [4].
Equivalently, let y = (y v ) v∈V ∈ R V be a vector such that . Then y is a basis of the null space of A(G) . Furthermore, if γ ∈ Z V and the condition (1) holds then there exists a solution ω ∈ Z E .
Proof. Recall that the existence of γ-R-flow is equivalent to the solvability of the system: 1. G is not bipartite if and only if it contains an odd cycle. So rank A(G) = |V | = n. Hence (2) is solvable. We now show that if γ ∈ Z V then there exists a solution ω such that 2ω ∈ Z V . Since G is not bipartite it contains an odd cycle C.
Since P is a cyclic matrix of an odd order det P = det P = 1. Note that P 2 corresponds also to a cyclic matrix of order n. That is, P 2 is similar to P . Hence det(I + P 2 ) = det(I + P ). Recall that the eigenvalues of P are all the n-th roots of 1. That is, det(λI n − P ) = λ n − 1. Let ζ 1 , . . . , ζ n be n − th roots of 1. So Here, σ i is the i − th elementary polynomial of ζ 1 , . . . , ζ n for i = 1, . . . , n. As ζ 1 , . . . , ζ n are the roots of λ n − 1 = 0, it follows that σ i = 0 for i = 1, . . . , n − 1.
Next , assume that ω(e) = 0 if e ∈ E(C). Let ω ∈ R E(C) be the unique solution of A(C)ω = γ. So the coordinates of ω coincide with coordinates of ω on E(C). Clearly, 2ω = 2A(C) −1 γ. Recall that A(C) −1 = adj (A(C)) det A(C) . Here, adj (A(C)) is the adjoint matrix of A(C) whose entries are minors of A of order n − 1. Since the entries of A(C) are integers it follows that the entries of adj (A(C)) are integers. Hence 2 det A(C)) adj A(C) = adj (C) and 2ω = adj (A(C))γ. So 2ω ∈ Z E(C) and 2ω ∈ Z E . We now assume that C is not Hamiltonian. Let V (C) = {v 1 , . . . , v l } where l is odd and 3 ≤ l < n. Delete the edge {v l , v 1 } from C to obtain a path Q. Extend Q to a spanning tree T of G. Let G = (V, E(T ) ∪ {v l , v 1 }). So G has exactly one odd cycle C. We claim that det A(G ) = ±2. Observe if we delete the edges of E(C) in G we obtain a forest. Hence, G contains at least one vertex u of degree 1. Expand det A(G ) by the row corresponding to u.
Let ω be the unique solution of (2) where ω(e) = 0 if e ∈ E(G ). The above arguments show that 2ω ∈ Z E .
2. Assume that G is bipartite and V = V 1 ∪ V 2 is the bipartite decomposition of V . Clearly, y A(G) = 0. Since rank A(G) = n − 1 then y spans the null space of A(G) . Hence the system (2) is solvable if and only if the condition (1) holds.
Let γ ∈ Z V and assume that the condition (1) holds. We now construct a solution ω ∈ Z E . Let T be a spanning tree of G. Let ω be the unique solution of (2) such that ω(e) = 0 if e ∈ E(T ). Recall that rank A(T ) = n−1.
Since y spans the null space of A(T ) it follows any n − 1 rows of A(T ) are linearly independent. Let B be a square submatrix of A obtained by deleting a row in A(T ) corresponding to a vertex v ∈ V . Denote by γ the vector obtained from γ be deleting coordinate γ(v). As A(T ) unimodular it follows that det B = ±1. Hence the solution of the system A(T )ω = γ is given by As ω(e) = ω(e ) for each e ∈ E(T ) we deduce that ω ∈ Z E .

Linear programming conditions for the existence of γ-intervalflows
In this section we apply linear programming methods to study the conditions for existence of γ-L-flow, where L is an interval of R. For simplicity of exposition we assume that L is a closed bounded interval [a, b]. Our methods and arguments are closed to those given in [8].
We denote [n] = {1, . . . , n}. We will identify and no ambiguity will arise. Let 1 m = 1 E be a column vector with m = |E| coordinates equal to 1. For two vectors We are looking for a solution of (2) such that Denote by I m the identity matrix of order m and by R + the set of nonnegative real numbers. Let d(G) = (deg(v)) v∈V ∈ R V be the degree sequence of G. Note that d(G) = A(G)1 m .
Lemma 2.2. Consider the system (2) satisfying the conditions (3). Then this system of equations is solvable if and only if the following conditions are satisfied: For each w ∈ R m + one has the inequality Proof. Clearly, the system (2) satisfying the conditions (3) is equivalent to the following conditions.
Farkas lemma claims [8] that the above system is solvable if and only if the following implication holds: where y = (y 1 , y 2 , y 3 , y 4 ), y 1 , y 2 ∈ R n , y 3 , y 4 ∈ R m . The equation y F = 0 is equivalent to The condition y ≥ 0 is equivalent to the inequalities (Note that if the above conditions hold, one can always choose y 1 , y 2 ≥ 0 such that z = y 2 − y 1 .) Clearly, these conditions are satisfiable for y 3 ≥ 0 and z = 0. Finally, the condition y f ≥ 0 is equivalent to the following the inequality Set w = y 3 and recall that A1 m = d(G) to deduce the lemma.
The condition (4) can be stated as the following nonlinear inequality in z ∈ R n . Let z = (z 1 , . . . , z n ) be an arbitrary vector in R n . Define w(z) = (w 1 (z), . . . , w m (z)) ∈ R+ m as follows: Then the condition (4) is equivalent to We state an equivalent necessary and sufficient condition for solvability of the system (2) satisfying the conditions (3) which can be stated in terms of nonnegative solutions of a corresponding variant of (2).

The system
is solvable.
We now give the condition for the existence of nonnegative solutions of (2).
Lemma 2.4. Consider the system (2) with γ = 0. Then this system has a nonnegative solution if and only if min{γ z, z ∈ R n , A z ≥ 0} = 0 (12) Proof. As in the proof of Lemma 2.2 the existence of nonnegative solutions of the system (2) is equivalent to the system The above system is solvable if and only if each nonnegative solution of y F = 0 satisfies the inequality y f ≥ 0. Let y = (y 1 , y 2 , y 3 ), where y 1 , y 2 ∈ R n and y 3 ∈ R m . Then the condition y ≥ 0 and F y = 0 are equivalent to the condition that y 3 = A z ≥ 0, where z = y 1 − y 2 . The condition y f ≥ 0 is equivalent to γ z ≥ 0. Note that if we choose z = 0 then y 3 = 0 and γz = 0. This implies (12).
We now restate our results for c-[a, b]-flows. That is, we let γ = c1 n .
Theorem 2.5. Let G = (V, E) be a simple undirected graph with no isolated vertices. The following are equivalent: 1. G has c-[a, b]-flow.
2. If G has a nonnegative c1 m − ad(G)-flow such that the value of this flow on each edge is at most b − a.
3. For each w ∈ R m + one has the inequality

The range of a 1-flow
Once a graph has been shown to have a γ-R-flow it is natural to ask which values the edge weights in such a flow can take. In this section we will look at questions of this type for the specific case of 1-sum flows. Given a 1-sum flow on a graph G we call the smallest interval which contains all the edge weights of the flow is called the range of the flow. A natural question now is: Given a graph G, which is the shortest interval L such that L is the range of a 1-sum flow on G? Starting from the other end we can also ask for a characterization of the graphs which have a 1-sum flow with range in some given interval L.
We will prove some results of both these forms. First we will look at 1-sum flows on trees, which have a unique 1-sum flow or none at all, and find the optimal range for this class of graphs. After that we do the same for graphs with a single cycle, and then give some bounds for the range of 1-sum flows on general graphs. After this we instead look at conditions guaranteeing that a graph has a 1-sum [1, 1]-flow, or a non-negative flow .

The range of 1-sum flows on trees
For a given graph G = (V, E) and the weight function ω : E → R, for each subset Q of E we denote by ω(Q) := e∈Q ω(e). We agree that ω(∅) = 0. In this section we analyze the the range of values of 1-flow on a tree T = (V, E) with n vertices, i.e. n = |V | and we let V = [n] = {1, . . . , n}. Recall that m = |E| = n − 1 and T is bipartite. Let A = A(T ). Then the system (2) is solvable if and only if the condition (1) holds. Assume that (1) holds.
We now estimate the coordinates of the solution of (2). We perform the following pruning procedure of a tree T . Let T 1 = T and P 1 ⊂ V be leaves. If T 1 = K 2 = K 1,1 or the star K 1,n−1 then we are done. Otherwise, let T 2 be the subtree of T 1 obtained by deleting the leaves P 1 and the corresponding |P 1 | edges. Denote by E(P 1 ) ⊂ E(T ) the subset of edges attached to P 1 . We now continue this process on T 2 . We obtain a sequence of subtrees Indeed, if we delete all leaves of T 1 which are neighbors of u, then it is possible that u is not a leaf of T 2 . On the other hand if u is a leaf in T 2 then u is not a leaf in T 1 and u has at least leaf neighbor in T 1 . We consider the system (2). Let γ (1) = (γ (1) (v)) v∈V 1 = γ and ω 1 (e) = γ (1) (v) for e ∈ E(P 1 ) and v ∈ e. The values of ω 1 (e) is the value of ω(e), where e is the unique edge in T 1 that contains the vertex v ∈ P 1 . Let , e ∈ E(P i ) be defined recursively as follows for i = 2, . . . , k: It is easy to see that each γ l can appear at most in one of the coordinates of γ (j) with coefficient ±1. (This is also follows from the condition (1).) Now consider T k . Assume first that T k = K 2 . So P k = {u, v}. In order to be able to solve the original system one needs that condition Let u be the center of the star. Then the solvability condition is: In both cases, since each γ(w) appears exactly once in some degree of T k with coefficient ±1, we deduce that this is equivalent to the fact that a basis to the null Theorem 3.1. Assume that a tree T has 1-flow, i.e. T is a balanced bipartite graph. Let T = T 1 ⊃ . . . ⊃ T k be the subtrees defined as above. Then the following conditions hold: 1. The unique flow is integer valued.
3. If i is even then ω i (e) ≤ 0 for e ∈ E(P i ). If i is odd then ω i (e) ≥ 1 for e ∈ E(P i ).

4.
be the bipartite decomposition of the balanced tree T . Then both V 1 (T ) and V 2 (T ) contain a leaf.
8. Assume that p 1 ≥ 4. Then n ≥ 6 and the flow is 9. In particular, the flow is in [2− n 2 , n 2 −2]. The lower bound achieved only for the unique tree T min , where T min is K 2 with appended n−2 2 vertices to each vertex of K 2 . For T min we obtain that the flow is 1-sum { 4−n 2 , 1} flow. The upper bound is obtained on for the unique tree T max , T max the path on 4 vertices, P L 4 , with n−4 2 vertices appended to each leaf of P L 4 . For T max we obtain the flow is 1-sum 10. The other optimal tree T opt , different from T max and T min , on n ≥ 8 vertices is obtained as follows. Take the path P L 4 : leaf at v 4 and one leaf at v 2 . Then this flows is 1-sum Proof.
3. Use (14), the fact that γ = 1 n and each ω 1 (e) = 1 for e ∈ E(P 1 ) to deduce that that each ω 2 (e) ≤ 0 for e ∈ E(P 2 ). Continuing in this manner, using (14) we deduce the claim. 4. Let E (P i ) be the subset of all edges in E(P i ) which are connected to P i+1 . (Note that some leaves in T i may be connected to nonleaf vertices in T i+1 .) Then summing the 1-flow on all vertices in P i , for i ≥ 2 we get Let i = 2. As ω 1 (e) = 1 for each e ∈ E(P 1 ) we deduce that p 2 ≤ ω 1 (E(P 1 )) + ω 2 (E(P 2 )) = p 1 + ω 2 (E(P 2 )). This establishes (16) for i = 2.
5. Assume to the contrary that V 1 (T ) does not have a leaf. So n − 1 = |E(T )| ≥ 2|V 1 (T )| = n as T is a balanced bipartite. This is impossible. Hence V 1 (T ) contains a leaf. Similarly, V 2 (T ) contains a leaf.
We will prove the claim on induction on n. In view of 6.-7. the claim holds for n = 2, 4. Assume that the claim holds for all even n, where n ≤ 2N . Assume that n = 2N + 2. In view of 6.-7. we assume that p ≥ 4. Let T be a balanced tree on 2N + 2 vertices with p ≥ 4 leaves. Let ω : Suppose first that deg(u 1 ), deg(v 1 ) ≥ 3. Then p = p − 2. By induction hypothesis This proves 8. in this case.
Suppose now that deg(u 1 ) = 2. Then ω(e 1 ) = 1 and ω(e 2 ) = 0. Delete vertices u, u 1 in T to obtain a balanced tree T with 2N vertices and p pendant vertices. Clearly p ≤ p. Also the 1-flow on T coincides. Use the induction hypothesis to deduce 8.

9-10
Clearly the maximal number of leaves in a balanced tree is p 1 = n − 2. This equality is achieved only for the tree T min . Apply 8. to deduce that the value of each 1-flow on a balanced tree on n vertices is not less than 4−n 2 . For T min the 1-flow is { 4−n 2 , 1}-flow. Other balanced tree on n vertices have at most n − 4 leaves. Use 8. to deduce that the value of each 1-flow on a balanced tree on n vertices is not more than n−4 2 . There are four nonisomorphic balanced trees with n − 4 leaves. T max , T opt and S 1 , S 2 . S 1 is obtained from T min by deleting one leaf in V 1 (T min ) and adjoining one vertex of a leaf in V 2 (T min ). S 2 is obtained from T max by removing one leaf from V 1 (T max ) and from V 2 (T max ) and adjoining these two leaves to v 2 and v 3 , respectively. For T max the 1-flow is

The range of 1-sum flows on Unicyclic graphs
We can also find a bound for the range of a 1-sum flow on a connected unicyclic graph, i.e. a graph which is obtained from a tree by adding a single edge. As for trees we call a vertex of degree one a leaf, and just as for trees the number of leaves turns out to control the range of the 1-sum flows. The bound is also strongly dependent on whether the graph is bipartite or not, with bipartite graphs giving us a narrower range, and in each case we find graphs for which the stated bound is optimal.
Theorem 3.2. Let G = (V, E) be a connected unicyclic graph, with |V | = n = |E|, which has a 1-sum flow. Assume that G has p ≥ 0 leaves. Then one of the following conditions holds: 1. p = 0. In this case G is a cycle and has a 1-sum { 1 2 }-flow 2. p = 1. If G has a 1-sum flow then it has a 1-[0, 1]-flow 3. p ≥ 2 and G is not bipartite. Then G has a 1-sum [1 − p, p]-flow.
This bound is optimal for the graph obtained by taking the disjoint union of a triangle and K 1,p+1 and joining one vertex on the triangle to one of the leaves of the K 1,p+1 . 4. p ≥ 2 and G is a balanced bipartite graph. Then G admits a 1-sum [1 − p 2 , p 2 ]-flow. This bound is optimal for the graph obtained by taking two copies of K 1,p/2 and joining the two high degree vertices by a six vertex path, giving a total of p + 8 vertices in the graph, and then adding an edge so that the middle 4 vertices of the path form a 4-cycle. Proof.
1. Set each the value on each edge to 1 2 . 2. If p = 1 then G consists of a cycle C joined to a path P by a single edge e = {u, v}, where u ∈ C. The flow on the path is uniquely determined, and is locally a flow with only values 0 and 1. If the flow on e is 0 we can set the weight on every edge in C to 1 2 and we are done. If the flow on e is 1 then C \ u is a path with an even number of vertices, since a 1-sum flow exists, and we can set the weight on a perfect matching in that path to 1 and 0 on the remaining edges, and so we have a flow on G with only weights 0 and 1.
3. We inductively assume that the theorem is true for smaller n and p. Let u and v be two leaves of G. If u is adjacent to a vertex w of degree 2 then G = G \ {u, w} has a 1-sum [1 − p, p]-flow, by induction on n, and by setting the weight on the edge {u, w} to 1 we can extend this to a 1-sum [1 − p, p]-flow on G, and we can follow the same procedure if v is adjacent to a vertex of degree 2. Hence we can assume that u and v are not adjacent to vertices of degree 2.
Since G is not bipartite there exists a walk W of odd length in G from u to v. By induction on p the graph G = G \ {u, v} has a 1-sum flow of the desired range. We can now build a 1-sum flow on G by setting the flow on the edges incident to u and v to 1, and then alternatingly subtract and add 1 to the weight of the edges along w. In this way we get a 1-sum flow on G, and since G had two less leaves than G and our modification changed each weight by at most 2, which happens if the edge was traversed twice by the walk W , we get a flow of the desired range.

In this case G is a balanced bipartite graph containing a single even cycle C.
Let u and v be two leaves of G belonging to different parts of the bipartition. If either one of them, say u, is adjacent to a vertex w of degree 2 then G = G \ {u, w} is also a balanced bipartite graph and, by induction on n, it has a 1-sum flow with the desired range. By setting the weight on the edge {w, u} to 1 and the weight on the other edge incident to w to 0, extend this to 1-sum flow of the desired range on G. Hence we can assume that u and v are not adjacent to vertices of degree 2.
Since u and v are in different parts there exists a path from u to v in G of odd length. By induction on p the graph G = G \ {u, v} has a 1-sum flow of the desired range. We can now build a 1-sum flow on G by setting the flow on the edges incident to u and v to 1, and then alternatingly subtract and add 1 to the weight of the edges along w. In this way we get a 1-sum flow on G, and since G had two less leaves than G and our modification changed each weight by at most 1 we get a flow of the desired range.

The range of 1-sum flows for general connected graphs
Our last two results give optimal bounds for the range of a 1-sum flow on very sparse graphs. For denser graphs there is a wider variety of behaviors and we do not have, or expect, an optimal bound in terms of any simple graph parameter. However, when one considers denser graphs G the expectation in general is that the optimal range should become narrower, especially since a 1-sum [a, b]-flow on a spanning subgraph can be extended to a 1-sum flow on G with range {0} ∪ [a, b] in the obvious way. For a graph with a k-factor this immediately leads to a 1-sum flow with a narrow range. We know that very dense graphs have 1-factors, and that random graphs with positive density have k-factors for quite large values of k, but there are of course quite dense graphs which do not even have a 1-factor. However all connected graphs have a spanning tree and using this fact our earlier results for trees implies a bound on the range for general graphs as well. This results can be sharpened a bit by including information about the independence number α(G) of G. In [7] it was proven that unless G is a cycle, a complete graph, or a balanced complete bipartite graph it has a spanning tree the end vertices of which form an independent set in G. Using this we get the following. 1. If G is k-regular then G has a 1-sum { 1 k }-flow.
3. If G is not regular, but is bipartite and balanced, then G has a 1- These bounds are quite far from the actual range for most graphs, since we know that for any fixed r a random graph with minimum degree at least r almost surely has an r-factor, and hence a 1-sum [0, 1 r ]-flow. If a graph G has k disjoint spanning trees and we have a 1-sum flow ω T on each tree T then the average of these flows, seen as flows on G, will also be a 1-sum flow on G. So in this case we can reduce the bounds in Corollary 3.4 by a factor of 1 k . Here we recall that Nash-Williams [13] and Tutte [18] have characterized the graphs which have k disjoint spanning trees, and so their characterization together with Corollary 3.4 give us a collection of graph classes with smaller ranges for their 1-sum flows.
In principle one could use the averaging procedure from the last paragraph for a collection of non-disjoint trees too. On one hand we might now be averaging several positive weights on a single edge, in which case we are no longer guaranteed to gain a factor of 1 k over the single tree bound but on the other hand we might have both positive and negative weights on the same edge, and the cancellation could lead to even greater gains. It would be interesting to see what can be said about a flow obtained in this way by taking a random collection of spanning trees in G.

Nonnegative 1-flows
Let Ω n ⊂ R n×n + be the set of doubly stochastic matrices. That is A = [a ij ] n i,j=1 is a nonnegative matrix such that each row and column has sum 1. Denote by P n ⊂ Ω n the group of n × n permutation matrices. Recall the classical result of G. Birkhoff [6], which is also called . Namely, the extreme points of doubly stochastic matrices are the permutation matrices.
Let Ω n,s ⊂ Ω n be the subset of symmetric doubly stochastic matrices. The following result due to M. Katz [12]: Let Ω n,s be the set of symmetric doubly stochastic matrices. Then A ∈ Ω n,s is an extreme point of Ω n,s if and only if A = 1 2 (Q + Q ) for some permutation matrix Q ∈ P n . Equivalently, there exists a permutation matrix P ∈ P n such that A = P BP , where B = diag(B 1 , . . . , B t ) and each B j is a doubly stochastic symmetric matrix of the following form:

Corollary 3.7.
Let Ω n,s,0 be the set of symmetric doubly stochastic matrices with zero diagonal. Then A ∈ Ω n,s,0 is an extreme point of Ω n,s,0 if and only if A = 1 2 (Q + Q ) for some permutation matrix Q ∈ P n which does not fix any i ∈ [n].
Equivalently, there exists a permutation matrix P ∈ P n such that A = P BP , where B = diag(B 1 , . . . , B t ) and each B j is a doubly stochastic symmetric matrix of the forms 2 or 3 given in Theorem 3.6.
Let H be a simple graph. H is called 1-factor, or perfect matching, if each connected component is K 2 . H is called {1, 2}-factor if each connected component of H is either K 2 or a cycle. G has 1-factor, or perfect matching, if G has a spanning subgraph which is 1-factor. G has {1, 2}-factor if G has a spanning subgraph which is {1, 2}-factor.
Birkhoff's theorem which shows that P n is the set of extreme points on Ω n .
Assume first that G has 1-[0, 1]-flow ω. Then A ∈ Ω n represents ω. So A = M j=1 a j P j where each P j ∈ P n , a j > 0 and M j=1 a j = 1. Hence each P j represents 1-factor of G. Vice versa, assume that G has 1-factor H. The arguments above imply thatω H is 1-[0, 1]-flow on G. As in the non-bipartite graph we deduce that G has 1-(0, 1]-flow if and only if each edge is covered by some 1-factor of G. The fundamental works of Tutte give necessary and sufficient conditions for existence 1 and {1, 2} factors [16,17]. Proof. We claim that G = (V, E) has a {1, 2}-factor. We prove this claim by induction on n = |V (G)|. For n = 3 the claim is trivial. Consider the block decomposition of G. It is well-known that every block of G is K 2 or an odd cycle, see [19]. Now, choose a leaf block of G. Obviously, it is an odd cycle C on 2l+1 vertices. Suppose first that C has a common vertex v, with another odd cycle C . Remove all vertices of C except v. The remaining graph G satisfies the assumption of the corollary. By the induction hypothesis G has a {1, 2}-factor. The subgraph of C on 2l vertices has a 1-factor. Hence G has a {1, 2}-factor.
It is left to discuss the case where the leaf cycle has one vertex v of degree 3 which is common with a K 2 -block. Consider the the shortest path, P , between v and another vertex of degree at least 3, say w ∈ V (C). Remove all the vertices on C and the path P except the vertex w. The remaining graph G = (V , E ) has a {1, 2}-factor by induction. Consider now the subgraph G 1 of G on the vertices V \ V . If the length of path is odd then G 1 has a {1, 2}-factor consisting of C and a matching, where the matching may be empty. If P is even then G 1 has a 1-factor. Hence G has a {1, 2}-factor.

Existence of 1-sum [−1, 1]-flows on graphs with δ(G) ≥ 2
In this section we assume that G is connected graph with the minimal degree δ(G) at least 2. We believe that it would be interesting to characterize the graphs which admit a 1-sum [−1, 1]-flow. This class clearly extends the class of graphs which have a 1-sum [0, 1]-flow, but the inclusion of negative edge weights adds more flexibility. Lemma 2.2 gives a necessary and sufficient conditions on the existence of these flows but at the moment we do not have a good interpretation of this result in terms of structural properties of the graphs.
However, we can show that not all graphs have a 1-sum [−1, 1]-flow, and in fact that given an integer t there are graphs of arbitrarily high edge-connectivity which does not have a 1-sum [−t, ∞)-flow.
We start out with a simple example and then proceed with the generalization to higher connectivity.   Consider two disjoint copies of K s,s(1+t)+1 . Call the vertex parts of the first one by (X, Y ) and the second one by (X , Y ), where |X| = |X | = s and |Y | = |Y | = s(1 + t) + 1. Choose an arbitrary vertex v ∈ X and join v to all vertices in X with the edges e 1 , . . . , e s and call the resulting graph by G. We claim that G is the desired graph. Clearly, G is an s-edge connected bipartite graph. Note that G is a balanced bipartite graph and so it admits a 1-sum R-flow. By contradiction assume that f is a 1-sum [−t, ∞)-flow of G. Then we have   As mentioned in the introduction the problem of finding a 1-sum L-flow when L is an interval is a linear programming problem. As soon as L is not an interval we are no longer working with a convex problem and many of the tools we have used so far do not apply. Nonetheless we shall prove some results for two cases of this type. First we will consider the real line with the single point 0 removed, a second we will look at the case when L consist of just a finite list of real numbers.
Question 4.1. Determine a necessary and sufficient condition under which a bipartite graph admits a 1-sum R * -flow or a 1-sum Z * -flow.
In this section we give an answer to this question.
It is not hard to see that if a graph G admits a 1-sum Z-flow, then the order of G should be even. In [4] it has been proved that a connected bipartite graph admits a 1-sum R-flow if and only if it is balanced. If V ⊂ m i=1 W i , then there exists a 0-sum R * -flow ω of G. It is obvious that there exists a suitable real number a such that ω + aω is a 1-sum R * -flow and we are done. Now, assume that there exists J ⊆ {1, . . . , m} such that for every j ∈ J, V = W j and for any j ∈ {1, . . . , m} \ J, V = W j . Since R is infinite, it is well-known that V ⊂ j∈J W j . So, there exists a vector α ∈ V , such that the jth component of α is non-zero for every j ∈ J. Now, let j ∈ {1, . . . , m} \ J. If e j is not a cut edge, then it is contained in an even cycle. If we assign 1 and −1 to all edges of this cycle, alternatively and assign 0 to all other edges of G, we obtain a vector in V \ W j , a contradiction. Hence e j is a cut edge of G. By assumption G \ {e j } has a non-balanced bipartite component H. Note that since G is balanced and H is not balanced, the other component, H , is not balanced too. Let H = (A, B) be two vertex parts of H and |A| < |B|. Without loss of generality assume that v ∈ A and e j is incident with v. Assign 1 to every vertex in (A \ {v}) ∪ B and assign |B| − |A| + 1 to v. Then by Theorem 3 of [4], H admits a flow such that s(v) = |B|−|A|+1 and s(x) = 1, for each x ∈ V (H)\{v}. Similarly, if H = (A , B ) and |A | < |B | and e j is incident with v ∈ A , then there exists a flow for H such that s(v ) = |B | − |A | + 1 and s(x) = 1, for each x ∈ V (H ) \ {v }. Since G is balanced, we have |A| + |B | = |A | + |B|. This yields that s(v) = s(v ). Now, assign |A| − |B| to e j to obtain a 1-sum flow for e j . Note that since V = W j , in any 1-sum R-flow of G, the value of e j should be |A| − |B|, which is non-zero. It is not hard to see that there exists a suitable a such that ω + aα is a 1-sum R * -flow of G, as desired.
Let G be a 2-edge connected bipartite graph and a < 0 and b > 0 be two real numbers and L = (a, b). Then G admits a 1-sum L-flow if and only if G admits a 1-sum L * -flow. To see this, by a theorem, G has a 0-sum R * -flow, say ω . Let ω be a 1-sum L-flow of G. Then if is small enough, ω + ω is a 1-sum R * -flow of G.

1-sum flows with a finite list
We can also let L be a finite list of allowed values, bringing us closer to the situation in the classical study of nowhere-zero flows of graphs.
Consider γ-flow on a connected G. Assume that γ ∈ C V and consider γ-C-flow on G. Lemma 2.1 applies also to C-flows. Let L = {t 1 , . . . , t k } be a subset of C of cardinality k. We now interested in the problem when there exists γ-L-flow. This is a problem in algebraic geometry. Define So, what we are asking for is a solution of the linear system (2) and the polynomial conditions P L (ω(e)) = 0 for each e ∈ E.
Since r = rank A(G) ∈ {n − 1, n} we have an overdetermined system of equations with m − r parameters which will have to satisfy m polynomial conditions. For relatively small graphs the existence of a solution can be determined by standard computer algebraic software like Mathematica.
In what follows we discuss very special flows and L using graph theory results.
Theorem 4.4. Let k be a positive integer and G be a connected k-regular graph of order n. Then the following hold: 1. If k is odd, then G admits a 1-sum {−1, 0, 1}-flow.
Proof. 1. First we assign a bipartite graph H to G. Suppose that V (G) = {1, . . . , n} and let H be a bipartite graph with two parts {x 1 , . . . , x n } and {y 1 , . . . , y n }. Join x i and y j if and only if two vertices i and j are adjacent in G.
Since H is a k-regular bipartite graph, the edges of H can be decomposed into k, 1-factors, F 1 , . . . , F k . Assign (−1) i−1 2 to all edges of F i , 1 ≤ i ≤ n. So, for each vertex v ∈ V (H), we have s(v) = 1 2 . For two adjacent vertices v i and v j in G, assume e ij is the edge between v i and v j . Let a ij be the value of the edge x i y j , 1 ≤ i, j ≤ n. Assign the value b ij = a ij + a ji to e ij . By our assumption, b ij ∈ {−1, 0, 1}. We have It is not hard to see that using this assignment we find a 1-sum {−1, 0, 1}-flow for G.