Accession Number : ADA185993
Title : The Perfectly Matchable Subgraph Polytope of an Arbitrary Graph.
Descriptive Note : Management science research rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Balas, Egon ; Pulleyblank, William R
PDF Url : ADA185993
Report Date : Aug 1987
Pagination or Media Count : 27
Abstract : The Perfectly Matchable Subgraph Polytope of a graph G=(V,E), denoted by PMS (G) is the convex hull of the incidence vectors of those X is a subset of V which induce a subgraph having a perfect matching. A linear system is described, whose solution set is PMS (G), for a general (nonbipartite) graph G. It can be derived via a projection technique from Edmonds' characterization of the matching polytope of G. This system can be deduced from the earlier bipartite case, by using the Edmonds- Gallai structure theorem. Finally, we characterize which inequalities are facet inducing for PMS (G), and hence essential. Keywords Projection; Perfectly Matchable Subgraph Polytype; Polyhedral Combinatorics; Matching Theory.
Descriptors : *GRAPHS, INDEX TERMS, LINEAR SYSTEMS, MATCHING, SOLUTIONS(GENERAL), THEOREMS, THEORY, COMBINATORIAL ANALYSIS, PROJECTIVE GEOMETRY
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE