User Tools

Site Tools


Garry Bowlin (Binghamton)

Maximum Frustration in Signed Complete Bipartite Graphs

Abstract for the Combinatorics Seminar 2009 February 9

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.

seminars/comb/abstract.200902bow.txt · Last modified: 2020/01/29 14:03 (external edit)