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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page