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.

اخر الاخبار

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

إقامة الجلسة البحثية الثانية باللغة الإنكليزية ضمن فعاليات مؤتمر أمير المؤمنين (عليه السلام)

إقامة الجلسة البحثية الأولى ضمن فعاليات المؤتمر الرابع لإحياء تراث أمير المؤمنين (عليه السلام)

اتحاد الأدباء يدعو إلى قراءة متعمقة في سيرة الإمام علي (عليه السلام)

جامعة الكوفة: محاور المؤتمر تناقش موضوعات التربية وبناء الإنسان عند الإمام علي (عليه السلام)

المزيد

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

دراسة تكشف تأثيرا مذهلا لـ"أوميغا 3"

دراسة تكشف تأثير المشي في الوقاية من الزهايمر

العصير ليس دائما الخيار الصحي.. حقائق يجب أن تعرفها

دراسة حديثة تعيد الجدل حول بدائل السكر

المزيد

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

"سيري".. نسخة جديدة تعتمد على الذكاء الاصطناعي من "غوغل"

ظاهرة نادرة.. "قمر القندس العملاق" الأقرب للأرض في 2025

بعثة صينية تمدد إقامتها في الفضاء.. وتواجه "المجهول"

أبوظبي تجمع رواد تكنولوجيا الذكاء والتنقل الذكي والروبوتات

المزيد

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

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