On The Adjacency Properties of Generalized Paley Graphs.
by
Watcharaphong Ananchen
School of Liberal Arts, Sukhothai Thammathirat Open University, Nonthaburi 11120 Thailand

Let m and n be non-negative integers and k a positive integer. A graph G is said to have property P(m, n, k) if for any m + n distinct vertices of G there are at least k other vertices, each of which is adjacent to the first m vertices but not adjacent to any of the latter n vertices. We know that almost all graphs have property P(m, n, k). However, for the case m, n >= 2, almost no graphs have been constructed, with the only known examples being Paley graphs which defined as follows. For q \equiv 1(mod 4) a prime power, the Paley graph G_q of order q is the graph whose vertices are elements of the finite field F_q; two vertices a and b are adjacent if and only if their difference is a quadratic residue. By using higher order residues on finite fields we can generate other classes of graphs which we refer to as generalized Paley graphs. For any m, n and k, we show that all sufficiently large (order) graphs obtained by taking cubic and quadruple residues satisfy property P(m, n, k).

Date received: August 9, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafn-03.