GRIDS IN RANDOM GRAPHS

Authors
DELAVEGA WF MANOUSSAKIS Y
Citation
Wf. Delavega et Y. Manoussakis, GRIDS IN RANDOM GRAPHS, Random structures & algorithms, 5(2), 1994, pp. 329-336
Citations number
9
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
5
Issue
2
Year of publication
1994
Pages
329 - 336
Database
ISI
SICI code
1042-9832(1994)5:2<329:GIRG>2.0.ZU;2-H
Abstract
Threshold probabilities for the existence in a random graph on n verti ces of a graph isomorphic to a given graph of order Cn and average deg ree at least three are investigated. In particular it is proved that t he random graph G(n, p) on n vertices with edge probability p = ((1 epsilon) log n/n)1/2, epsilon < 1, contains a square grid on epsilonn/ 2 vertices. (C) 1994 John Wiley & Sons, Inc.