This lecture is the Ph.D. thesis defense of Mr. Bowlin. His examining committee is Laura Anderson, Steven Dougherty (University of Scranton), Fernando Guzman, and Thomas Zaslavsky (chair).
Everyone is welcome to attend.
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, and negative if the product is negative. 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.
I prove two results about the maximum frustration of a complete bipartite graph Kl,r with l left vertices and r right vertices. First, it is bounded above by
r (l/2) { 1 − C( l-1, [(l-1)/2] ) }
where [x] is the greatest integer in x.
Second, for each Kl,r there is essentially at most one sign labelling that attains this bound.
The main techniques used are linear programming and matrix theory. I derived the bound using linear programming, and my matrix results prove that the signed graphs which attain the bound are unique. With these two results, I was able to compute exact formulas for the maximum frustration of Kl,r when l < 7.
In addition to the main theorems, I have two results about the frustration index of signed complete bipartite graph when the bipartite adjacency matrix is a Hadamard matrix.