¡@

Definition of the circular flow number of a graph

¡@

Suppose G  is an undirected graph. We view G  as a symmetric directed graph, with each edge replaced by a pair of opposite arcs. Denote by A(G) the arc set of G. For an arc  a  of G,  denote by  a^- the opposite arc of a. A chain of G is a mapping f  from A(G)  to R  such that for each arc a of G,

f(a^-) = - f(a).

For a subset X  of V(G),  denote by [X, V\X] the set of arcs from X to V\X.  We call [X, V\X] a cut of G. A flow of G is a chain f  such that for each cut [X, V\X],

sum_{ a \in [X, V\X] } f(a) = 0.

Suppose r >= 2 is a real number. An r-flow is a flow f such that for each arc  a   of G,

1 <= | f(a) | <= r-1.

The circular flow number of G is defined as

Phi_c(G) = inf { r :  G admits an r-flow }.

An integer flow is a flow f  such that for each arc a,  f(a)  is an integer. A nowhere zero k-flow  is an integer flow f  such that for each arc a,

1 <= | f(a) | <= k-1.

The flow number (or flow index) of G  is defined as

Phi(G) = min { k : G  admits a nowhere zero k-flow }.

¡@