7
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Aug 14, 2020 at 0:52
  • $\begingroup$ true, but I think there must be something more general, an analogue of that for all cuts ? $\endgroup$
    – Mircea
    Commented Aug 14, 2020 at 13:18

0

Reset to default

You must log in to answer this question.