The perfectly matchable subgraph polytope of a bipartite graph

摘要: Abstract : The following type of problem arises in practice: a node-weighted graph G, find minimum weight node set that satisfies certain conditions and, addition, induces perfectly matchable subgraph G. This has led us to study the convex hull incidence vectors sets induce subgraphs which we call polytype For case when G is bipartite, give linear characterization this polytype, i.e., specify system inequalities whose basic solutions are We derive result by three different approaches, using programming duality, projection, and lattice polyhedra, respectively. projection approach used here for first time as proof method polyhedral combinatorics, seems have many similar applications. Finally, completely characterize facets our separate essential defining from redundant ones. (Author)