Get Math Help

GET TUTORING NEAR ME!

(800) 434-2582

By submitting the following form, you agree to Club Z!'s Terms of Use and Privacy Policy

    Home / Get Math Help

    Matching Defect Polynomial

    Definition

    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.

    Related Wolfram Language symbol

    GraphData

    Back to List | POWERED BY THE WOLFRAM LANGUAGE