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

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.