{"id":"arxiv/2601.11119","url":"https://arxiv.org/abs/2601.11119","tags":["math.CO","cs.DM","math.OC"],"score":0,"title":"Bond Polytope under Vertex- and Edge-sums","domain":"math.CO","source":"arxiv","authors":["Petr Kolman","Hans Raj Tiwary"],"reviews":0,"subject":"math.CO","summary":"A cut in a graph $G$ is called a {\\em bond} if both parts of the cut induce connected subgraphs in $G$, and the {\\em bond polytope} is the convex hull of all bonds. Computing the maximum weight bond is an NP-hard problem even for planar graphs. However, the problem is solvable in linear time on $(K_5 \\setminus e)$-minor-free graphs, and in more general, on graphs of bounded treewidth, essentially due to clique-sum decomposition into simpler graphs. We show how to obtain the bond polytope of graphs that are $1$- or $2$-sum of graphs $G_1$ and $ G_2$ from the bond polytopes of $G_1,G_2$. Using…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-16","reactions":{}}