Matching Number

The (upper) matching number  of graph , sometimes known as the edge independence number, is the size of a maximum independent edge set. Equivalently, it is the degree of the matching-generating polynomial

(1)

where  is the number of -matchings of a graph . The notations , , or  are sometimes also used.

The matching number is also the size of a largest maximal independent edge set, while the size of a smallest maximal independent edge set is called the lower matching number.

 satisfies

(2)

where  is the vertex count of ,  is the floor function. Equality occurs only for a perfect matching, and graph  has a perfect matching iff

(3)

where  is the vertex count of .

The matching number  of a graph  is equal to the independence number  of its line graph .

The König-Egeváry theorem states that the matching number equals the vertex cover number (i.e., size of the smallest minimum vertex cover) are equal for a bipartite graph.

If a graph  has no isolated points, then

(4)

where  is the matching number,  is the size of a minimum edge cover, and  is the vertex count of  (West 2000).

Precomputed matching numbers for many named graphs are available in the Wolfram Language using GraphData[graph, "MatchingNumber"].

---

REFERENCES

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

اخر الاخبار

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

المجمع العلمي يجري الاختبارات النظرية للدورات القرآنية في النجف الأشرف

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

قرب مقام الإمام المهدي (عجّل الله فرجه).. قسم الصناعات ينهي أعمال إنشاء سور على ضفة نهر الحسينية

قسم العلاقات العامة ينظم برنامجًا ثقافيًّا لوفد طلابي من جامعات البصرة

المزيد

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

حالة صحية شائعة قد تُخفي "إنذارا مبكرا" للإصابة بالسرطان !

"أوميغا 3" صديق القلب.. هل يربك سكر الدم؟

بدائل لليمون.. 8 إضافات للماء تعزز فوائده الصحية

دراسة: محاولة متعمدة لنشر الإنفلونزا تنتهي بـ"مفاجأة"

المزيد

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

سلامة الأطفال: سبع قواعد ذهبية للركوب الآمن بالسيارة

توقع خطير لماسك: الروبوتات ستتفوق على البشر من حيث العدد

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

"ميتا" توقف وصول المراهقين إلى شخصيات الذكاء الاصطناعي ؟

المزيد

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

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