A PROPERTY OF RANDOM GRAPHS
Louis Caccetta, Kousalya Devi Vijayan · 2001
A graph G is said to have property P(k) if for any two sets A and B of vertices of G with A n B = $J and /A u BI = k , there is a vertex u P A u B which is joined to every vertex of A and not joined to any vertex of B . Note that if a graph G has property P(k) , then the complement GC of G also has property P(k) . If we specify the sizes of A and B as x and y respectively (x + y = k) then we denote the above property by P(k:x,y) I Let f(n) be the largest integer for which there exists a graph on n vertices having property P(f(n)) .