The perfect matching polytope and solid bricks |
| |
Authors: | Marcelo H de Carvalho Cludio L Lucchesi USR Murty |
| |
Institution: | a UFMS, Campo Grande, Brasil;b University of Waterloo, Waterloo, Canada;c UNICAMP, Campinas, Brasil |
| |
Abstract: | The perfect matching polytope of a graph G is the convex hull of the set of incidence vectors of perfect matchings of G. Edmonds (J. Res. Nat. Bur. Standards Sect. B 69B 1965 125) showed that a vector x in QE belongs to the perfect matching polytope of G if and only if it satisfies the inequalities: (i) x 0 (non-negativity), (ii) x(∂(v))=1, for all v V (degree constraints) and (iii) x(∂(S)) 1, for all odd subsets S of V (odd set constraints). In this paper, we characterize graphs whose perfect matching polytopes are determined by non-negativity and the degree constraints. We also present a proof of a recent theorem of Reed and Wakabayashi. |
| |
Keywords: | Matchings The perfect matching polytope Bricks |
本文献已被 ScienceDirect 等数据库收录! |
|