𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The size of the largest hole in a random graph

✍ Scribed by Tomasz Łuczak

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
775 KB
Volume
112
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 up to a factor of 2.

📜 SIMILAR VOLUMES

The largest induced tree in a sparse ran
The largest induced tree in a sparse random graph
✍ W. Fernandez de la Vega 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 2 views

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently lar

On the Largest Component of the Random G
On the Largest Component of the Random Graph at a Nearcritical Stage
✍ Boris Pittel 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 225 KB

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.

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

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

The Largest Parity Demigenus of a Simple
The Largest Parity Demigenus of a Simple Graph
✍ Thomas Zaslavsky 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 421 KB

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according as its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is Euler characteristic) over all surfaces S in which 1 can be parity embedded. We calcul