##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 572.05036

**Autor: ** Caccetta, Louis; Erdös, Paul; Vijayan, K.

**Title: ** A property of random graphs. (In English)

**Source: ** Ars Comb. 19A, 287-294 (1985).

**Review: ** A graph is said to have property P(n) if for any two disjoint vertex sets A and B with |A\cup B| = k there is another vertex which is joined to every vertex in A and no vertex in B. Let f(n) be the largest integer such that there is a graph of order n having property P(f(n)). Probabilistic methods are used to prove bounds on f(n).

**Reviewer: ** O.Frank

**Classif.: ** * 05C35 Extremal problems (graph theory)

60C05 Combinatorial probability

05C80 Random graphs

**Keywords: ** extremal graphs; Probabilistic methods

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag