关键词: Wings, matching, reconstruction

Abstract:

Let I with |I| = k be a matching of a graph G (briefly, I is called a k-matching). If I is not a proper subset of any other matching of G, then I is a maximal
k-matching and m(gk,G) is used to denote the number of maximal k-matchings of G.Let gk be a k-matching of G, if there exists a subset {e1, e2, · · ·, ei} of E(G) \ gk, i  1,such that (1) for any j 2 {1, 2, · · · , i}, gk + {ej} is a (k + 1)-matching of G; (2) for any f 2 E(G) \ (gk [ {e1, e2, · · · , ei}), gk + {f} is not a matching of G; then gk is called an iwings k-matching of G and mi(gk,G) is used to denote the number of i wings k-matchings
of G. In this paper, it is proved that both mi(gk,G) and m(gk,G) are edge reconstructiblefor every connected graph G, and as a corollary, it is shown that the matching polynomial is edge reconstructible.

Key words: Wings, matching, reconstruction