**Problem of the Week**

**Math Club**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

seminars:comb:abstract.200907bow

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 *K _{l,r}* with

where [x] is the greatest integer in x. Second, for each

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 *K _{l,r}* when

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.

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

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported