- Unbalanced cycle: A cycle with an odd number of negative edges.
Justification for the name: in such a cycle, familiar social expectations—such as a friend of a friend is a friend—fail to hold.
One may also use the term negative cycle because the product of the signs of all edges is negative. - Balanced set: a set of vertices which does not induce an unbalanced cycle.
A signed graph \( \large (G, \sigma) \) is said to be balanced if \(\large V(G) \) is a balanced set.
Historically, the term balance is taken from a paper on psychology, Heider [1946]. It was formalized for graphs in Harary [1953/1954], where the term signed graphs was first introduced.
The concept of splitting cycles into two types, however, is older and appears in the first book on graph theory as is noted later in this page. - Switching at a vertex \(\large v\) : to multiply the sign of all edges incident to \(\large v\) by \(\large - \).Note: a loop, being multiplied by both ends, is unaffected. Switching at a set \(\large X \) of vertices is equivalent to multiply the signs of all edges in the cut \( \large X,V(G)\ X \) by \(\large -\). In some literature the term resigning is used in place of switching which should be read as re-signing. In such literature it is also common to use the terms odd, even, and bipartite for, respectively, negative (edge), positive (edge), and balanced.
- Geometric meaning of switching: For a geometric presentation of switching at a vertex we may use double cover of \(\large \widehat{G} \). To switch at a vertex \( \large x \) is the same as swapping the placing of \( \large x^+ \) and \( \large x^- \). Then parallel edges, one with \( \large x^+ \) as an end and the other with \( \large x^- \) as end, become crossing edges and crossing edges become parallel.
- Switching equivalent: Two signed graphs \( \large (G, \sigma_1) \) and \( \large (G, \sigma_2) \) where one is obtained from the other by a switching at a subset of vertices. In such a case the signatures \( \large \sigma_1 \) and \( \large \sigma_2 \) are said to be switching equivalent. This is an equivalence relation on the set of all signature functions on .
Remark: Switching is what separates signed graphs from 2-edge-colored graphs.
Question. Given signed graphs \( \large (G, \sigma_1) \) and \( \large (G, \sigma_2) \) how to decide if they are switching equivalent?
Answer. Take a fundamental set \( \large \mathcal{C} \) of cycles of \( \large G \) and test if \( \large \sigma_1(C)=\sigma_2(C) \) for every member \(\large C \) of \(\large \mathcal{C} \). If for at least one choice this does not hold, then the two signatures are not equivalent. If it holds for all members of \( \large \mathcal{C} \), then they are indeed equivalent. The proof of this is hidden in the proof of the following theorem of Zaslavsky.
Theorem. Two signed graphs \( \large (G, \sigma_1) \) and \( \large (G, \sigma_2) \) are switching equivalent if and only if \(\large \sigma_1(C)=\sigma_2(C) \) holds for any cycle of \(\large G\).
Proof. Since we can work on connected components separately, we assume \(\large G \) is connected. We only need to show that if \(\large \sigma_1(C)=\sigma_2(C) \) holds for every cycle of \( \large G \), then \( \large \sigma_1 \) and \( \large \sigma_2 \) are switching equivalent. Take spanning tree \( \large T \) and switch \( \large (G, \sigma_2) \) to \( \large (G, \sigma'_2) \) so that on the edges of \( \large T \) the signs agree with the signature \( \large \sigma_1\). The claim is that now \(\large \sigma_1=\sigma'_2 \). That is because each other edge \(\large e \) induces a unique cycle \( \large C_{e} \) in \(\large T+e \) and the sign of this cycle uniquely determines the values of \(\large \sigma_1(e) \) and \(\large \sigma'_2(e) \). As for each cycle we have \(\large \sigma_1(C)=\sigma_2(C)=\sigma'_2(C) \), we have \(\large \sigma_1(e)=\sigma'_2(e) \) for every edge \(\large e\).
The special case of the theorem where \( \large \sigma_1 \) is the homogeneous function \( \large \sigma(e)=+\), is about asking if \(\large (G, \sigma_2)\) is balanced. This case was addressed in Harary [1953/1954]. The generalization is from Zaslavsky [1982].
The set of negative cycles of a signed graph \( \large (G, \sigma) \) satisfies the following \( \large \Theta\)-property:
\( \large \Theta\)-property. Given three \(\large (x-y)\)-paths, of the three closed walks formed by any pair, an even number of them are negative. That is to say, either none of them is negative or two of them. The first place where the study of a family of cycles satisfying this property appears is the first book on graph theory which is written in German and translated to English about 6 decades later: Kőnig[1936] (English translation Kőnig[1990]). To name such family of cycles Kőnig used the German term "gerades System von Zykeln" (literally: “even system of cycles”) to describe a set of cycles satisfying this property.
In modern language the following can be found in: Naserasr–Sopena–Zaslavsky[2021]
Theorem. A set \(\large \mathcal{C}\) of cycles of a graph \(\large G \) is the set of negative cycles of a signed graph \(\large (G,\sigma)\) if and only if it satisfies the \( \large \Theta\)-property.
References:
Heider [1946]: Fritz Heider. Attitudes and Cognitive Organization. The Journal of Psychology, 21(1) (1946), 107–112. DOI Harary [1953]: Frank Harary. On the notion of balance of a signed graph. Michigan Math. J. 2 (1953/1954), 143–146. Zaslavsky [1982]: Thomas Zaslavsky. Signed graphs. In L. W. Beineke & R. J. Wilson (Eds.), Selected Topics in Graph Theory, Vol. 2 (pp. 143–167). Academic Press. DOI Kőnig [1936]: Dénes Kőnig. Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft. Kőnig [1990]: Dénes Kőnig. Theory of Finite and Infinite Graphs. Translated and edited by R. McEliece. Birkhäuser, Boston. DOI Naserasr–Sopena–Zaslavsky [2021]: Reza Naserasr, Éric Sopena, and Thomas Zaslavsky.Homomorphisms of signed graphs: an update. European Journal of Combinatorics, 91 (2021), 103222. DOI
Signed graphs