Minimum Edge Cover

A minimum edge cover is an edge cover having the smallest possible number of edges for a given graph. The size of a minimum edge cover of a graph is known as the edge cover number of  and is denoted .

Every minimum edge cover is a minimal edge cover (i.e., not a proper subset of any other edge cover), but not necessarily vice versa.

Only graphs with no isolated points have an edge cover (and therefore a minimum edge cover).

A minimum edge cover of a graph can be computed in the Wolfram Language with FindEdgeCover[g]. There is currently no Wolfram Language function to compute all minimum edge covers of a graph.

If a graph  has no isolated points, then

where  is the matching number and  is the vertex count of  (Gallai 1959, West 2000).

---

REFERENCES

Gallai, T. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eőtvős Sect. Math. 2, 133-138, 1959.

Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 318, 2003.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 178, 1990.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

اخر الاخبار

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

بمشاركة 142 منتسبًا.. قسم الشؤون الدينية يختتم دورته الفقهية التطويرية السادسة

قسم بين الحرمين: قدمنا أكثر من 50 ألف وجبة إفطار للزائرين خلال شهر رمضان المبارك

المجمع العلمي يختتم نشاطاته القرآنية الرمضانية في المثنى

بتوجيهٍ من وكيل المرجعية العُليا.. العتبة العباسية المقدسة تطلق حملةً لجمع التبرّعات إلى الشعبَينِ الإيراني واللبناني

المزيد

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

كوب قبل النوم.. مشروب طبيعي يحارب الأرق

دون أدوية.. طريقة طبيعية لخفض ضغط الدم بفعالية مذهلة

المعكرونة ليست عدوك.. كيف تصبح جزءا من وجبة صحية متوازنة؟

دراسة: تناول القهوة يوميا يخفض خطر الإصابة بالاضطرابات النفسية

المزيد

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

علماء روس يخططون لبناء منشأة للكشف عن المادة المظلمة

ثاني أكسيد الكربون ليس تهديدا للمناخ فقط.. بل لصحة الإنسان أيضا!

ديدان الأرض تكشف تلوث التربة بالمعادن الثقيلة

خبير أرصاد جوية: ظاهرة النينيو القادمة قد تكون الأقوى خلال 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