# Maximum Frustration in Bipartite Signed Graphs

Keywords:
Graph Theory, Signed Graphs, Frustration Index, Balance, Line Index

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