acyclic polynomial | matching defect polynomial | reference polynomial

A k-matching in a graph G is a set of k edges, no two of which have a vertex in common (i.e., an independent edge set of size k). Let Φ_k be the number of k-matchings in the graph G, with Φ_0(G) = 1 and Φ_1(G) = m the number of edges of G. Then the matching polynomial is defined by μ(x) = sum_(k = 0)^(ν(G)) (-1)^k Φ_k x^(n - 2k), where n = left bracketing bar G right bracketing bar vertex count of G and ν(G) is the matching number (which satisfies ν(G)<=⌊n/2⌋, where ⌊x⌋ is the floor function). The matching polynomial is also known as the acyclic polynomial (Gutman and Trinajstić 1976, Devillers and Merino 2000), matching defect polynomial, and reference polynomial.

characteristic polynomial | Hosoya index | independent edge set | matching | matching-generating polynomial | matching number | perfect matching

GraphData