Forced Edges and Graph Structure.

For a degree sequence, we define the set of edges that appear in every labeled realization of that sequence as forced, while the edges that appear in none are define as forbidden. We examine the structure of graphs in which the degree sequences contain either forced or forbidden edges. The results include the determination of the structure of the forced or forbidden edge sets, the relationship between the sizes of forced and forbidden sets for a sequence, and the structural consequences to their realizations.

A Sufficient Condition for Graphic Sequences with Given Largest and Smallest Entries, Length, and Sum.

We give a sufficient condition for a nonnegative integer list to be graphic based on its largest and smallest elements, length, and sum. This bound generalizes a result of Zverovich and Zverovich.

Fast Sequential Creation of Random Realizations of Degree Sequences.

We examine the problem of creating random realizations of very large degree sequences. Although fast in practice, the Markov chain Monte Carlo (MCMC) method for selecting a realization has limited usefulness for creating large graphs because of memory constraints. Instead, we focus on sequential importance sampling (SIS) schemes for random graph creation.

Threshold Digraphs.

A digraph whose degree sequence has a unique vertex labeled realization is called threshold. In this paper we present several characterizations of threshold digraphs and their degree sequences, and show these characterizations to be equivalent. Using this result, we obtain a new, short proof of the Fulkerson-Chen theorem on degree sequences of general digraphs.