### 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$.#### Keywords

Graph Theory; Signed Graphs; Frustration Index; Balance; Line Index