 TOPICS  # Flow Polynomial

Let denote the number of nowhere-zero -flows on a connected graph with vertex count , edge count , and connected component count . This quantity is called the flow polynomial of the graph , and is given by   (1)   (2)

where is the rank polynomial and is the Tutte polynomial (extending Biggs 1993, p. 110).

The flow polynomial of a graph can be computed in the Wolfram Language using FlowPolynomial[g, u].

The flow polynomial of a planar graph is related to the chromatic polynomial of its dual graph by (3)

The flow polynomial of a bridged graph, and therefore also of a tree on nodes, is 0.

The flow polynomials for some special classes of graphs are summarized in the table below.

 graph flow polynomial book graph  cycle graph  ladder graph  prism graph  web graph 0 wheel graph  Linear recurrences for some special classes of graphs are summarized below.

 graph order recurrence antiprism graph 4 book graph 2 ladder graph 1 prism graph 3 wheel graph 2 Chromatic Polynomial, Rank Polynomial, Tutte Polynomial

## Explore with Wolfram|Alpha More things to try:

## References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 110-111, 1993.Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications I: The Tutte Polynomial." 28 Jun 2008. http://arxiv.org/abs/0803.3079.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, p. 370, 2001.

Flow Polynomial

## Cite this as:

Weisstein, Eric W. "Flow Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FlowPolynomial.html