I was reading Graph Theory and Complex Networks by Maarten van Steen. I was reading about undirected signed graphs in the section on social network analysis, which contains the following theorem:

An undirected signed graph G is balanced if and only if V(G) can be partitioned into two disjoint subsets $V_0$ and $V_1$ such that the following two conditions hold:
(1) $E^-(G) = \{\langle x, y \rangle | x \in V_0, y \in V_1 \}$
(2) $E^+(G) = \{ \langle x, y \rangle | x, y \in V_0 \thinspace or \thinspace x, y \in V_1 \}$

Case #1 (especially given the prior description in the book) seems to me to be quite a bit like the criteria for a bipartite graph. Does this theorem basically mean that if you had a graph where every single edge was signed negative (i.e. $E^-(G) = E(G)$) then $G$ must be bipartite?

Edit: A signed graph is a simple graph in which each edge is labeled with a sign (- or +). An undirected sign graph is balanced when all of its cycles are positive. The sign of a set of edges can be found by multiplying all of the signs of the edges in the set; the result of multiplying two signs is negative if exactly one of the signs is negative and is positive otherwise (so, for example, - * - = + and - * + = -).

  • $\begingroup$ Hello, can you please include the definition of what a balanced signed graph is ? $\endgroup$ – HereToRelax Apr 8 at 1:37
  • $\begingroup$ @HereToRelax I updated. $\endgroup$ – EJoshuaS - Reinstate Monica Apr 8 at 2:19

Yes I think it is true.

Claim: an undirected balanced signed graph $G$ in which every edge is negative is bipartite. We claim the sets $V_0$ and $V_1$ are a bipartition.

We must show that if $\{x,y\}\in E$ then $x\in V_0$ and $y\in V_1$ or $x\in V_1$ and $y\in V_0$.

Notice that because every edge is negative we have $\{x,y\}\in E^-$, and because $G$ is balanced, it follows $x_0\in V_0$ and $y\in V_1$ or $x\in V_1$ and $y\in V_0$, as desired.

So indeed every signed graph in which every edge is negative must be bipartite.

On the other hand if we have a bipartite graph and we make every edge negative, the graph will be balanced, as every cycle of the graph must be of even length (and hence the product of an even number of $-1$'s is positive).

I'm not entirely happy with how I wrote it, what do you think?


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.