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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength