ON THE ADJACENCY PROPERTIES OF PALEY GRAPHS

In the application of graph theory to problems arising in network desi gn, the requirements of the network can be expressed in terms of restr ictions on the values of certain graph parameters such as connectivity , edge-connectivity, diameter, and independence number. In this paper, we focus on networks whose requirements translate into adjacency rest rictions on the graph representing the network. More specifically, a g raph G is said to have property P(m,n,k) if for any set of m + n disti nct vertices there are at least k other vertices, each of which is adj acent to the first m vertices but not adjacent to any of the latter n vertices. The problem that arises is that of characterizing graphs hav ing property P(m,n,k). In this paper, we present properties of graphs satisfying the adjacency property. In particular, for q = 1(mod 4), a prime power, the Paley graph G(q) of order q is the graph whose vertic es are elements of the finite field F(q); two vertices are adjacent if and only if their difference is a quadratic residue. For any m, n, an d k, we show that all sufficiently large Paley graphs satisfy P(m,n,k) .