Abstract

Rich McBride (ISU), The convex hull of degree sequences of signed graphs

Abstract: A sequence of integers (x1,x2,..., xn) is the degree sequence of a signed graph if åxi is even and for all disjoint subsets S,T of {1,2,...,n} with a = |S|, b = |T|,

å{xi : i in S}-å{xj: j in T} £ a(n-1) + b(n-1) -2ab.

The set of all real n-tuples satisfying the above system of inequalities is a convex polytope. In this talk we determine many properties of this polytope and in particular how it relates to the convex hull of degree sequences of signed graphs.


Last modified: Tuesday, Apr. 17, 2006