On Fractional Realizations of Graph Degree Sequences

Michael D. Barrus

Abstract


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.


Keywords


Fractional graph theory; Degree sequences; 0/1-polytopes

Full Text: PDF