Let $(V, E, w)$ a weighted graph, with vertices $V$, edges $E$, and signed weight $w:E\to \mathbb R$.

I am interested to know other popular properties that are known to imply, or are equivalent to, the requirement that all cuts of the graph are positive. This part in boldface means that every time $V$ is partitioned in two nonempty sets $V=V_1 \cup V_2$, the sum of $w$ over the edges with one end in $V_1$ and the other in $V_2$, needs to be $>0$.

And by any chance, does this property have a fancy name?

  • $\begingroup$ This is almost obvious, but a necessary condition is that the sum of all the edge weights must be positive (since the sum of weights incident to every vertex must be positive). $\endgroup$ – Louis D Aug 14 '20 at 0:52
  • $\begingroup$ true, but I think there must be something more general, an analogue of that for all cuts ? $\endgroup$ – Mircea Aug 14 '20 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.