×

zbMATH — the first resource for mathematics

On a facet of the balanced subgraph polytope. (English) Zbl 0643.05059
A class of graphs called wreaths is introduced. It is shown that the wreaths induce some new facets of the bipartite subgraph polytope studied in [F. Barahona, M. Groetschel and A. R. Mahjoub, Math. Oper. Res. 10, 340-358 (1985; Zbl 0578.05056)]. Similar results hold also for signed graphs. The relation between associated polytopes is discussed.

MSC:
05C99 Graph theory
90C27 Combinatorial optimization
05C75 Structural characterization of families of graphs
PDF BibTeX XML Cite