Regular Weighted Graphs Without Positive Cuts

Abstract

For a simple and finite graph \(G = (V,E)\), let \(w_{\max}(G)\) be the maximum total weight \(w(E) = \sum_{e\in E} w(e)\) of \(G\) over all weight functions \(w: E \to \{-1,1\}\) such that \(G\) has no positive cut, i.e., all cuts \(C\) satisfy \(w(C) \leq 0\).

For \(r \geq 1\), we prove that \(w_{\max}(G) \leq -\frac{|V|}{2}\) if \(G\) is \((2r-1)\)-regular and \(w_{\max}(G) \leq -\frac{r|V|}{2r+1}\) if \(G\) is \(2r\)-regular. We conjecture the existence of a constant \(c\) such that \(w_{\max}(G) \leq -\frac{5|V|}{6} + c\) if \(G\) is a connected cubic graph and prove a special case of this conjecture. Furthermore, as a weakened version of this conjecture, we prove that \(w_{\max}(G) \leq -\frac{2|V|}{3}+\frac{2}{3}\) if \(G\) is a connected cubic graph.