Vertex Cover Polynomial

Let  be the number of vertex covers of a graph  of size . Then the vertex cover polynomial  is defined by

(1)

where  is the vertex count of  (Dong et al. 2002).

It is related to the independence polynomial  by

(2)

(Akban and Oboudi 2013).

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

The following table summarizes closed forms for the vertex cover polynomials of some common classes of graphs (cf. Dong et al. 2002).

graph
Andrásfai graph
barbell graph
book graph	{2[x(x+1)]^n+x[x(x+2)]^n}" src="https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline14.svg" style="height:22px; width:240px" />
cocktail party graph
complete bipartite graph
complete bipartite graph
complete graph
complete tripartite graph
crown graph
cycle graph
empty graph
gear graph	{[x(2+x-sqrt(x(4+x)))]^n+[x(2+x+sqrt(x(4+x)))]^n})/(2^n)" src="https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline29.svg" style="height:34px; width:361px" />
helm graph	{[x(1+x-sqrt((1+x)(5+x)))]^n+[x(1+x+sqrt((1+x)(5+x)))]^n}" src="https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline30.svg" style="height:28px; width:639px" />
ladder rung graph
Möbius ladder
path graph
prism graph
star graph
sun graph
sunlet graph
wheel graph

Equivalent forms for the cycle graph  include

			(3)
			(4)

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
complete graph	2
complete tripartite graph	2
crossed prism graph	2
crown graph	3
cycle graph	2
empty graph	1
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

---

REFERENCES

Akban, S. and Oboudi, M. R. "On the Edge Cover Polynomial of a Graph." Europ. J. Combin. 34, 297-321, 2013.

Csikvári, P. and Oboudi, M. R. "On the Roots of Edge Cover Polynomials of Graphs." Europ. J. Combin. 32, 1407-1416, 2011.

Dong, F. M.; Hendy, M. D.; Teo, K. L.; and Little, C. H. C. "The Vertex-Cover Polynomial of a Graph." Discr. Math. 250, 71-78, 2002.

اخر الاخبار

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

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

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

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

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

المزيد

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

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

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

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

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