✦ LIBER ✦

The degree sequence of a random graph. I. The models

✍ Scribed by Brendan D. McKay; Nicholas C. Wormald

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 246 KB
Volume: 11
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199709)11:2<97::aid-rsa1>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of 1 random graphs with n vertices and m edges. For a wide range of values of m, this 2 distribution is almost everywhere in close correspondence with the conditional distribution ÄŽ . < 4 X , . . . , X Ý X sm , where X , . . . , X are independent random variables, each having Ž .

📜 SIMILAR VOLUMES

A RANDOM GRAPH MODEL FOR THE FINAL-SIZE

A RANDOM GRAPH MODEL FOR THE FINAL-SIZE DISTRIBUTION OF HOUSEHOLD INFECTIONS

✍ M. N. ISLAM; C. D. O'SHAUGHNESSY; B. SMITH 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB 👁 1 views

In epidemiological/disease control studies, one might be interested in estimating the parameters community probability infection (CPI) and the household secondary attack rate (SAR), as introduced by Longini and Koopman. The quasi-binomial distribution I (QBD I) with parameters n, p and 0, introduced

On some simple degree conditions that gu

On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs

✍ Vu, Van H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 2 views

It is well known that almost every graph in the random space G(n, p) has chromatic number of order O(np/ log(np)), but it is not clear how we can recognize such graphs without eventually computing the chromatic numbers, which is NP-hard. The first goal of this article is to show that the above-menti

On a random graph with immigrating verti

On a random graph with immigrating vertices: Emergence of the giant component

✍ David J. Aldous; Boris Pittel 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB 👁 2 views

A randomly evolving graph, with vertices immigrating at rate n and each possible edge appearing at rate 1/n, is studied. The detailed picture of emergence of giant components with O n 2/3 vertices is shown to be the same as in the Erdős-Rényi graph process with the number of vertices fixed at n at t

Degree of segregation and coalescence ra

Degree of segregation and coalescence rate parameter in the random coalescence model for a stirred reactor

✍ P. F. Marconi; N. Vatistas 📂 Article 📅 1983 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 473 KB 👁 1 views

Flexible Modelling of the Covariance Mat

Flexible Modelling of the Covariance Matrix in a Linear Random Effects Model

✍ Emmanuel Lesaffre; David Todem; Geert Verbeke; Mike Kenward 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB 👁 2 views

A degree condition for the existence of

A degree condition for the existence of regular factors inK1,n-free graphs

✍ Ota, Katsuhiro; Tokuda, Taro 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 260 KB 👁 1 views

A graph is called K1,.-free if it contains no K l , n as an induced subgraph. Let n ( r 3), r be integers (if r is odd, r 2 n -1). We prove that every Kl,,-free connected graph G with rlV(G)I even has an r-factor if its minimum degree is at least This degree condition is sharp.