Premium
Random graphs with forbidden vertex degrees
Author(s) -
Grimmett Geoffrey,
Janson Svante
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20307
Subject(s) - mathematics , combinatorics , vertex (graph theory) , random graph , giant component , poisson distribution , graph , random regular graph , discrete mathematics , 1 planar graph , chordal graph , statistics
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