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