Random graphs with forbidden vertex degrees

We study the random graph G n ,λ/ n conditioned on the event that all vertex degrees lie in some given subset $ {\cal S} $ of the nonnegative integers. Subject to a certain hypothesis on $ {\cal S} $ , the empirical distribution of the vertex degrees is asymptotically Poisson with some parameter $ \hat{\mu} $ given as the root of a certain “characteristic equation” of $ {\cal S} $ that maximizes a certain function $ {\psi_{\cal S}(\mu)} $ . Subject to a hypothesis on $ {\cal S} $ , we obtain a partial description of the structure of such a random graph, including a condition for the existence (or not) of a giant component. The requisite hypothesis is in many cases benign, and applications are presented to a number of choices for the set $ {\cal S} $ including the sets of (respectively) even and odd numbers. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010