Flow Polynomial
المؤلف:
Biggs, N. L
المصدر:
Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press
الجزء والصفحة:
...
19-4-2022
1979
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
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  |
![((u-1)[(-1)^(n+1)+(u-1)^n])/u](https://mathworld.wolfram.com/images/equations/FlowPolynomial/Inline22.svg) |
cycle graph  |
 |
ladder graph  |
 |
prism graph  |
![(-1)^n-(u-2)^n+(u-3)^n+[(-1)^n(u-3)+(u-3)^n]u](https://mathworld.wolfram.com/images/equations/FlowPolynomial/Inline28.svg) |
| 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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
