The matching polynomial of a regular graph
Mathematics and Computer Science
The matching polynomial of a graph has coefficients that give the number of matchings in the graph. For a regular graph, we show it is possible to recover the order, degree, girth and number of minimal cycles from the matching polynomial. If a graph is characterized by its matching polynomial, then it is called matching unique. Here we establish the matching uniqueness of many specific regular graphs; each of these graphs is either a cage, or a graph whose components are isomorphic to Moore graphs. Our main tool in establishing the matching uniqueness of these graphs is the ability to count certain subgraphs of a regular graph.
Beezer, Robert A., and Ej Farrell. 1995. "The Matching Polynomial of a Regular Graph." Discrete Mathematics 137(1-3): 7-18.