zbMATH — the first resource for mathematics

Random graphs. (English) Zbl 0567.05042
London-Orlando etc.: Academic Press (Harcourt Brace Jovanovich, Publishers). XVI, 447 p. hbk: £52.00; $ 58.50; pbk: £26.00; $ 29.95 (1985).
This is a comprehensive account of the theory of random graphs. A typical problem is to determine the probability that a large random graph \(G_ n\) has some particular property P given that the number (or expected number) of edges in \(G_ n\) is some particular function of n. As the fraction of edges present in \(G_ n\) increases from zero to one, the structure of a typical random graph \(G_ n\) passes through several distinct stages; and for various properties P there is a fairly narrow interval in which the probability that \(G_ n\) has property P increases from near zero to near one. This book contains sixteen chapters dealing with topics such as the degree sequence, sparse components, the giant component, connectivity, the diameter, long paths and cycles, cliques, and independent sets; there are also chapters on Ramsey theory, random matrices and permutations, and sorting algorithms. There are numerous exercises and an extensive bibliography of over 750 references. This is an impressive book that should be of value of anyone interested in the subject.
Reviewer: J.W.Moon

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C80 Random graphs (graph-theoretic aspects)
05Cxx Graph theory