Matching-Generating Polynomial

A -matching in a graph  is a set of  edges, no two of which have a vertex in common (i.e., an independent edge set of size ). Let  be the number of -matchings of the graph , with  (since the empty set consisting of no edges is always a 0-matching) and  the edge count of . Then the matching-generating polynomial directly encodes the numbers of -independent edge sets of a graph  and is defined by

(1)

where  is the matching number of .

The matching-generating polynomial is multiplicative with respect to disjoint unions of graphs, so for graphs  and ,

(2)

where  denotes a graph union.

The matching-generating polynomial  is related to the matching polynomial  by

(3)

(Ellis-Monaghan and Merino 2008) and

(4)

The matching-generating polynomial is closely related to the independence polynomial. In particular, since independent edge sets in the line graph  correspond to independent vertex sets in the original graph , the matching-generating polynomial of a graph  is equal to the independence polynomial of the line graph of  (Levit and Mandrescu 2005).

A graph  has a perfect matching iff

(5)

where  is the vertex count of .

Precomputed matching-generating polynomials for many named graphs in terms of a variable  will be obtainable using GraphData[graph, "MatchingGeneratingPolynomial"][x].

The following table summarizes closed forms for the matching-generating polynomials of some common classes of graphs. Here,  is a confluent hypergeometric function of the second kind,  is a Laguerre polynomial, and  is a Lucas polynomial.

graph
complete graph
complete bipartite graph
cycle graph
empty graph
star graph

---

REFERENCES

Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008. http://arxiv.org/abs/0806.4699.

Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 (Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.

اخر الاخبار

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

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

شعبة الخطابة الحسينية النسوية تقيم برنامجًا لإحياء ليالي القدر وذكرى شهادة الإمام علي (عليه السلام)

المجمع العلمي يحيي ذكرى شهادة الإمام علي (عليه السلام) في بغداد

قسم الشؤون الفكرية يطلق عددًا خاصًّا من نشرة الخميس في ذكرى شهادة الإمام علي (عليه السلام)

المزيد

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

خمسة مؤشرات صحية مهملة قد تنقذ حياتك

متى تكون الحمى طبيعية؟

التدخين الإلكتروني يهدد قلبك.. دراسة جديدة تكشف مخاطر ارتفاع ضغط الدم

دراسة تكشف فائدة بعض أنواع الشاي في محاربة الاكتئاب

المزيد

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

الجهاز المناعي يظهر دورا غير متوقع في صحة العظام

ابتكار من جامعة الشارقة منخفض التكلفة للحماية من الزلازل

اكتشاف تأثير غير متوقع للكاكاو على وظائف الدماغ

باحثون يرصدون أثر تغيّر المناخ في دم البشر

المزيد

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

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