TOPICS
Search

Nowhere-Zero Flow


A nowhere-zero k-flow on a graph G consists of an orientation of its edges and an integer value f(e) assigned to each graph edge such that 0<|f(e)|<k and the sum of the values on edges directed into each graph vertex equals the sum on edges directed out of it (Tutte 1954). Existence of such a flow is independent of the chosen orientation.

For positive integer u, the number of nowhere-zero u-flows on a graph is given by its flow polynomial.


See also

Flow Polynomial, Tutte 4-Flow Conjecture

Explore with Wolfram|Alpha

References

Tutte, W. T. "A Contribution to the Theory of Chromatic Polynomials." Canad. J. Math. 6, 80-91, 1954. https://doi.org/10.4153/CJM-1954-010-9.

Cite this as:

Weisstein, Eric W. "Nowhere-Zero Flow." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Nowhere-ZeroFlow.html

Subject classifications