Problem of the Week
Hilton Memorial Lecture
The frustration index of a signed graph is the smallest number of edges whose sign reversal yields a balanced signed graph (i.e., where all circles have positive sign product). In 1966, Petersdorf showed that the maximum frustration of a signed complete graph Kn is equal to floor[(n-1)2/4], and it is achieved by the all-negative signing. This is the only interesting graph family for which the problem has been solved. Using convex geometry, I show that the maximum frustration for a signed Kl,r is bounded above by
r · (l/2) · [ 1 − 2−(l−1) binom( l−1, floor[(l−1)/2] ) ]
and that this bound is achieved by a signing of Kl,2l−1.