数学物理学报(英文版) ›› 2004, Vol. 24 ›› Issue (4): 603-607.
许宝刚
Xu Baogang
摘要:
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.
中图分类号: