Edge Cover Polynomial

 

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

(1)

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

Cycle graphs and complete bipartite graphs are determined by their edge cover polynomials (Akban and Oboudi 2013).

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

(2)

The edge cover polynomial satisfies

(3)

where  is the vertex count of a graph  and  is its independence polynomial (Akban and Oboudi 2013).

The following table summarizes sums for the edge cover polynomials of some common classes of graphs (Akban and Oboudi 2013).

graph
complete bipartite graph
complete graph
cycle graph
path graph

The following table summarizes closed forms for the edge cover polynomials of some common classes of graphs.

graph
book graph
cycle graph
helm graph
path graph
star graph
sunlet graph

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

graph	order	recurrence
cycle graph	2
book graph	3
gear graph	4
helm graph	2
ladder graph	3
Möbius ladder	4
path graph	2
prism graph	4
star graph	1
sunlet graph	1
web graph	2
wheel graph	4

---

REFERENCES

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

اخر الاخبار

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

العتبة العباسية المقدسة تدعو جامعة السليمانية إلى المشاركة في الحفل المركزي لتخرج طلبة الجامعات العراقية

قسم حفظ النظام يعلن استحداث شعبة الإعداد البدني لتدريب المنتسبين

العتبة العباسية المقدسة تدعو جامعة أربيل التقنية إلى المشاركة في الحفل المركزي لتخرج طلبة الجامعات العراقية

قسم العلاقات العامة يبحث مع قسم الشؤون الخدمية استعدادات حفل تخرج طلبة الجامعات العراقية

المزيد

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

"سر" ليلي خفي.. عادة بسيطة قد تنقذ قلبك دون أن تشعر

اكتشاف جديد يفتح الباب أمام علاج إدمان التدخين

9 أطعمة طبيعية لصحة المفاصل وتخفيف آلامها والتهاباتها

قبل النوم بلحظات.. "ثمرة ذهبية" تهدئ جسدك وعقلك

المزيد

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

دماغك في حالة بناء دائم.. 5 محطات تغير شخصيتك جذريا

حقيقة "نهاية الرجال".. جدل علمي حاد ونظريات مثيرة

دراسة تكشف سر "نفوق 60 ألف بطريق".. أين وكيف ولماذا؟

أستراليا تختبر واقعية مدى السيارات الكهربائية.. و4 علامات تجارية تخفق

المزيد

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

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