¡@
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 }.
¡@