✦ LIBER ✦

On the Largest Component of the Random Graph at a Nearcritical Stage

✍ Scribed by Boris Pittel

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 225 KB
Volume: 82
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.2033

No coin nor oath required. For personal study only.

✦ Synopsis

The random graphs G(n, Pr(edge)= p), G(n, *edges=M) at the critical range p=(1+*n &1Â3 )Ân and M=(nÂ2)(1+*n &1Â3 ) are studied. The limiting distribution of the largest component size is determined.

📜 SIMILAR VOLUMES

The size of the largest hole in a random

The size of the largest hole in a random graph

✍ Tomasz Łuczak 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 775 KB

Let H(n, p) denote the size of the largest induced cycle in a random graph C(n, p). It is shown that if the expected average degree of G(n, p) is a constant larger than 1, then H(n, p) is of the order n with probability 1 -o(l). Moreover, for C(n, p) with large average degree, H(n, p) is determined

The largest component in a random subgra

The largest component in a random subgraph of the n-cycle

✍ Gyula O.H. Katona; Louis V. Quintas 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 214 KB

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

An upper bound on the size of the larges

An upper bound on the size of the largest cliques in a graph

✍ Alain Billionnet 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB 👁 1 views

## Abstract We produce in this paper an upper bound for the number of vertices existing in a clique of maximum cardinal. The proof is based in particular on the existence of a maximum cardinal clique that contains no vertex __x__ such that the neighborhood of __x__ is contained in the neighborhood

On the largest tree of given maximum deg

On the largest tree of given maximum degree in a connected graph

✍ Y. Caro; I. Krasikov; Y. Roditty 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 1 views

## Abstract We prove that every connected graph __G__ contains a tree __T__ of maximum degree at most __k__ that either spans __G__ or has order at least __k__δ(__G__) + 1, where δ(__G__) is the minimum degree of __G.__ This generalizes and unifies earlier results of Bermond [1] and Win [7]. We als

An upper bound on the size of a largest

An upper bound on the size of a largest clique in a graph

✍ Dennis P. Geoffroy; David P. Sumner 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB 👁 1 views

## Abstract A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point‐determining graph is the set __G__^O^ of all vertices, __v__, such that __G__–__v__ is point determining. In this paper we show that the size, ω(__G__), of a maximum clique in __G__ sat