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