zbMATH — the first resource for mathematics

Facets of the bipartite subgraph polytope. (English) Zbl 0578.05056
Let \(G=(V,E)\) be an undirected finite graph. For an edge set \(F\subseteq E\) the vector \(x^ F\in R^ E\) with \(x^ F_ e=1\) if \(e\in F\) and \(x^ F_ e=0\) if \(e\not\in F\) is called the incidence vector of \(F\). The bipartite subgraph polytope of the graph \(G\) is then the convex hull in \(R^ E\) of the incidence vectors of all edge sets of bipartite subgraphs of G. The authors obtain for this polytope \(P_ B(G)\) facet defining inequalities with integral coefficients in the interval \([0,n^ 2/4]\) where \(n\) is the order of the given graph \(G\), by showing first that all complete subgraphs of odd order and all so called bicycle wheels contained in \(G\) induce facets of \(P_ B(G)\). New facet defining inequalities of \(P_ B(G)\) are then constructed from known ones by using several methods such as contraction and splitting of nodes, odd subdivisions of the edges and subdivisions of all edges of a cut.
Reviewer: H.Kramer

05C85 Graph algorithms (graph-theoretic aspects)
52B99 Polytopes and polyhedra
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI