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)\le 0$.

For $r\ge 1$, we prove that $w_{max}(G)\le -\frac{|V|}{2}$ if $G$ is $(2r-1)$-regular and $w_{max}(G)\le -\frac{r|V|}{2r+1}$ if $G$ is $2r$-regular. We conjecture the existence of a constant $c$ such that $w_{max}(G)\le -\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)\le -\frac{2|V|}{3}+\frac{2}{3}$ if $G$ is a connected cubic graph.