The convex hull of degree sequences of signed graphs

As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27–36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n -tuples satisfying this system of linear inequalities is a polytope P n . In this paper, we show that P n is the convex hull of the set of degree sequences of signed graphs of order n . We also determine many properties of P n , including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147–153].