×

zbMATH — the first resource for mathematics

A property of random graphs. (English) Zbl 0572.05036
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

MSC:
05C35 Extremal problems in graph theory
60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite