Rank Polynomial

The rank polynomial  of a general graph  is the function defined by

(1)

where the sum is taken over all subgraphs (i.e., edge sets) and the rank  and co-rank  of the subgraph  is given by

			(2)
			(3)

for a subgraph with  vertices,  edges, and  connected components (Biggs 1993, p. 73).

The rank polynomial is multiplicative over graph components, so for a graph  having connected components , , ..., the rank polynomial of  itself is given by

(4)

It is given in terms of the Tutte polynomial  as

(5)

The chromatic polynomial  and rank polynomial of a general graph  with  vertices are related by

(6)

(Biggs 1993, p. 75).

Trivially,

(7)

where  is the number of edges of the graph (Biggs 1993, p. 74).

The following table summarizes rank polynomials for some common classes of graphs.

graph	rank polynomial
banana tree
book graph	{1+x[3+x(3+y)]}^n)/y" src="https://mathworld.wolfram.com/images/equations/RankPolynomial/Inline26.svg" style="height:33px; width:265px" />
centipede graph
cycle graph
gear graph
ladder rung graph
pan graph
path graph
star graph
sunlet graph

The following table summarizes recurrence equations for rank polynomials of common classes of graphs.

graph	recurrence
book graph
cycle graph
gear graph
helm graph
ladder graph
pan graph
sunlet graph
wheel graph

Nonisomorphic graphs do not necessarily have distinct rank polynomials. The following table summarizes some co-rank graphs.

rank polynomial	graphs
1	empty graph
	, , , , , , path graph
	triangle graph, , , , ,
	, , , , , , , , -fiveleaper graph, -fiveleaper graph, -knight graph, 2-ladder rung graph, path graph
	claw graph, , , , , , , , , , , , , , , -fiveleaper graph, 3-ladder rung graph, path graph
	paw graph, , , , , , , , )
	square graph, , , , ,
	diamond graph, , , ,
	tetrahedral graph, , , ,

---

REFERENCES

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 73, 97, and 101, 1993.

Godsil, C. and Royle, G. "Rank Polynomial" and "Evaluations of the Rank Polynomial." §15.9-15.10 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 355-358, 2001.

اخر الاخبار

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

قسم الشؤون الطبية يقدم الخدمات الصحية والعلاجية لزائري مدينة سامراء

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

المجمَع العلمي ووفد وزارة التربية يبحثان سبل التعاون المشترك

قسم الشؤون الفكرية يصدر العدد 192 من مجلة الرياحين للأطفال

المزيد

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

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

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

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

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