TOPICS
Search

Flow Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Let C^*(u) denote the number of nowhere-zero u-flows on a connected graph G with vertex count n, edge count m, and connected component count c. This quantity is called the flow polynomial of the graph G, and is given by

C^*(u)=(-1)^mR(-1,-u)
(1)
=(-1)^(m-n+c)T(0,1-u),
(2)

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

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

The flow polynomial C_G^*(u) of a planar graph G is related to the chromatic polynomial of its dual graph G^* by

C_G^*(u)=u^(-1)pi_(G^*)(u).
(3)

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

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

graphflow polynomial
book graph S_(n+1) square P_2((u-1)[(-1)^(n+1)+(u-1)^n])/u
cycle graph C_nu-1
ladder graph P_2 square P_n(u-1)(u-2)^(n-1)
prism graph Y_n(-1)^n-(u-2)^n+(u-3)^n+[(-1)^n(u-3)+(u-3)^n]u
web graph0
wheel graph W_n(-1)^(n+1)(u-2)+(u-2)^(n-1)

Linear recurrences for some special classes of graphs are summarized below.

graphorderrecurrence
antiprism graph4
book graph S_(n+1) square P_22p_n(u)=(u-2)p_(n-1)(u)+(u-1)p_(n-2)(u)
ladder graph P_2 square P_n1p_n(u)=(u-2)p_(n-1)(u)
prism graph Y_n3p_n(u)=2(u-3)p_(n-1)(u)+(-u^2+7u-11)p_(n-2)(u)-(u-3)(u-2)p_(n-3)(u)
wheel graph W_n2p_n(u)=(u-3)p_(n-1)(u)+(u-2)p_(n-2)(u)

See also

Chromatic Polynomial, Rank Polynomial, Tutte Polynomial

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Flow Polynomial

Cite this as:

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

Subject classifications