Graphs with a prescribed adjacency property.
Watcharaphong Ananchuen, Lou Caccetta · 1992
A graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices of G there are at least k other vertices, each of which is adjacent to the first m vertices of the set but not adjacent to any of the latter n vertices. The problem that arises is that of characterizing graphs having property P(m,n,k). In this paper, we present properties of graphs satisfying the adjacency property. In addition, for small m and n we show that all sufficiently large Paley graphs satisfy P(m,n,k).