On the Bond Polytope

Markus Chimani, Martina Juhnke-Kubitzke, Alexander Nover

Given a graph $G=(V,E)$, the maximum bond problem searches for a maximum cut $\delta (S)\subseteq E$ with $S\subseteq V$ such that $G[S]$ and $G[V\setminus S]$ are connected. This prob…