On Fractional Realizations of Graph Degree Sequences

  • Michael D. Barrus
Keywords: Fractional graph theory, Degree sequences, 0/1-polytopes


We introduce fractional realizations of a graph degree sequence and a closely associated convex polytope. Simple graph realizations correspond to a subset of the vertices of this polytope; we characterize degree sequences for which each polytope vertex corresponds to a simple graph realization. These include the degree sequences of threshold and pseudo-split graphs, and we characterize their realizations both in terms of forbidden subgraphs and graph structure.

Article Number