
Accession Number : ADA185993
Title : The Perfectly Matchable Subgraph Polytope of an Arbitrary Graph.
Descriptive Note : Management science research rept.,
Corporate Author : CARNEGIEMELLON 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