Maximum Frustration in Bipartite Signed Graphs

Abstract

A signed graph is a graph where each edge is labeled as either positive or negative. A circle is positive if the product of edge labels is positive. The frustration index is the least number of edges that need to be removed so that every remaining circle is positive. The maximum frustration of a graph is the maximum frustration index over all possible sign labellings. We prove two results about the maximum frustration of a complete bipartite graph $K_{l,r}$, with $l$ left vertices and $r$ right vertices. First, it is bounded above by\[ \frac{lr}{2}\left(1-\frac{1}{2^{l-1}}\binom{l-1}{\lfloor \frac{l-1}{2}\rfloor}\right).\] Second, there is a unique family of signed $K_{l,r}$ that reach this bound. Using this fact, exact formulas for the maximum frustration of $K_{l,r}$ are found for $l \leq 7$.