Title

The matching polynomial of a regular graph

Document Type

Article

Publication Date

1995

Publication Title

Discrete Mathematics

Department

Mathematics and Computer Science

Abstract

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.

Volume

137

Issue

13

pp.

2014-07-18

ISSN

0012-365X

Link to Full Text

Share

COinS