Independence Polynomial

Let  be the number of independent vertex sets of cardinality  in a graph . The polynomial

(1)

where  is the independence number, is called the independence polynomial of  (Gutman and Harary 1983, Levit and Mandrescu 2005). It is also goes by several other names, including the independent set polynomial (Hoede and Li 1994) or stable set polynomial (Chudnovsky and Seymour 2004).

The independence polynomial is closely related to the matching polynomial. In particular, since independent edge sets in the line graph  correspond to independent vertex sets in the original graph , the matching-generating polynomial of a graph  is equal to the independence polynomial of the line graph of  (Levit and Mandrescu 2005):

(2)

The independence polynomial is also related to the clique polynomial  by

(3)

where  denotes the graph complement (Hoede and Li 1994), and to the vertex cover polynomial by

(4)

where  is the vertex count of  (Akban and Oboudi 2013).

The independence polynomial of a disconnected graph is equal to the product of independence polynomials of its connected components.

Precomputed independence polynomials for many named graphs in terms of a variable  can be obtained in the Wolfram Language using GraphData[graph, "IndependencePolynomial"][x].

The following table summarizes closed forms for the independence polynomials of some common classes of graphs. Here, , , and .

graph
Andrásfai graph
barbell graph
book graph
centipede graph
cocktail party graph
complete bipartite graph
complete graph
complete tripartite graph
crossed prism graph
crown graph
cycle graph
gear graph
helm graph
ladder graph
ladder rung graph
Möbius ladder
pan graph
path graph
prism graph
star graph
sun graph
sunlet graph
triangular graph
wheel graph

The following table summarizes the recurrence relations for independence polynomials for some simple classes of graphs.

graph	order	recurrence
Andrásfai graph	3
antiprism graph	3
barbell graph	3
book graph	2
centipede graph	2
cocktail party graph	2
complete bipartite graph	2
crossed prism graph	2
crown graph	3
cycle graph	2
gear graph	3
helm graph	3
ladder graph	2
ladder rung graph	1
Möbius ladder	3
pan graph	2
path graph	2
prism graph	3
star graph	2
sun graph	2
sunlet graph	2
web graph	3
wheel graph	3

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

	independence polynomial	graphs
4		, path graph
4		paw graph, square graph
5		,
5		butterfly graph, house graph, kite graph,
5		banner graph, bull graph,
5		fork graph, ,
5		house X graph, wheel graph
5		gem graph, , -lollipop graph
5		cycle graph , -tadpole graph
5		dart graph, complete bipartite graph

The independence polynomial of a tree is unimodal, and the independence polynomial of a claw-free graph is logarithmically concave.

---

REFERENCES

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.

Chudnovsky, M. and Seymour, P. "The Roots of the Stable Set Polynomial of a Claw-Free Graph." 2004. http://www.math.princeton.edu/÷mchudnov/publications.html.

Gutman, I. and Harary, F. "Generalizations of the Matching Polynomial." Utilitas Mathematica 24, 97-106, 1983.

Hoede, C. and Li, X. "Clique Polynomials and Independent Set Polynomials of Graphs." Disc. Math. 125, 219-228, 1994.

Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 

(Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.

اخر الاخبار

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

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

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

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

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

المزيد

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

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

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

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

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