Nowhere-zero flow

In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected (by duality) to coloring planar graphs.

Definitions

Let G = (V,E) be a directed graph and let M be an abelian group. A map φ: E → M is a flow, M-flow, or M-circulation if for every vertex v ∈ V

\sum _{e\in \delta ^{+}(v)}\varphi (e)=\sum _{e\in \delta ^{-}(v)}\varphi (e),

where δ⁺(v) denotes the set of edges out of v and δ⁻(v) denotes the set of edges into v. Sometimes, this condition is referred to as Kirchhoff's law.^[1] If φ(e) ≠ 0 for every e ∈ E, we call φ a nowhere-zero flow.

If k is an integer and |φ(e)| < k for every edge e, then φ is called a k-flow.

Other notions

Let G = (V,E) be an undirected graph. An orientation of E is a modular k-flow if

|\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\pmod {k}}

for every vertex v ∈ V.

Properties

Orientation independence. Modify a nowhere-zero flow φ on a graph G by choosing an edge e, reversing it, and then replacing φ(e) with -φ(e). After this adjustment, φ is still a nowhere-zero flow. Furthermore, if φ was originally a k-flow, then the resulting φ is also a k-flow. Thus, the existence of a nowhere-zero M-flow or a nowhere-zero k-flow is independent of the orientation of the graph. Thus, an undirected graph G is said to have a nowhere-zero M-flow or nowhere-zero k-flow if some (and thus every) orientation of G has such a flow.
If G admits a NZ k-flow then it admits a NZ h-flow where $h\geq k$ .
The set of NZ flows do not necessarily form a group as the sum of two flows on one edge may add to 0.

Flow polynomial

Let N(G) be the number of NZ M-flows on G. It satisfies the deletion–contraction formula N(G) = N(G / e) - N(G \ e).

Using this and induction, it can be shown that N(G) is a polynomial in |M| - 1 where |M| is the order of the group M.

This implies that two groups of equal order have an equal number of NZ flows. The order is the only group parameter that matters, not the structure of M.

N(G) is called the flow polynomial of G and abelian group M.

A graph G has a NZ M-flow iff it has a NZ |M|-flow.^[1]

The above results were proved by Tutte in 1953 when he was studying the Tutte polynomial, a generalization of the flow polynomial.^[2]

Flow-coloring duality

Let G = (V,E) be a directed bridgeless graph drawn in the plane, and assume that the regions of this drawing are properly k-colored with the colors {0, 1, 2, .., k – 1}. Now, construct a map φ: E(G) → {–(k – 1), ..., –1, 0, 1, ..., k – 1} by the following rule: if the edge e has a region of color x to the left and a region of color y to the right, then let φ(e) = x – y. It is an easy exercise to show that φ is a k-flow. Furthermore, since the regions were properly colored, φ is a nowhere-zero k-flow. It follows from this construction, that if G and G* are planar dual graphs and G* is k-colorable, then G has a nowhere-zero k-flow. Tutte proved that the converse of this statement is also true. Thus, for planar graphs, nowhere-zero flows are dual to colorings. Since nowhere-zero flows make sense for general graphs (not just graphs drawn in the plane), this study can be viewed as an extension of coloring theory for non-planar graphs.

Theory

Unsolved problem in mathematics

Does every bridgeless graph have a nowhere zero 5-flow? Does every bridgeless graph that does not have the Petersen graph as a minor have a nowhere zero 4-flow?

References

^ ^a ^b Diestel, Reinhard, 1959- Verfasser. Graph theory. ISBN 9783662536216. OCLC 1048203362. {{cite book}}: |last= has generic name (help)CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
^ Tutte, William Thomas (1953). "A contribution to the theory of chromatic polynomials". {{cite journal}}: Cite journal requires |journal= (help)
^ F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Set. B, 26 (1979), 205-216.
^ P. D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130-135.
^ 5-flow conjecture, Open Problem Garden.
^ 4-flow conjecture, Open Problem Garden.