On graphs and digraphs with prescribed properties
by
Watcharaphong Ananchuen
School of Liberal Arts, Sukhothai Thammathirat Open University, Thailand

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(\funcmod 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 residue on finite field we can generate other class of graphs. For any m, n and k, we show that all sufficiently large graphs obtained by taking cubic residue satisfy property P(m, n, k).

A digraph D is said to have property Q(n, k) if for every subset of n vertices of D is dominated by at least k other vertices. Let q \equiv 5(\funcmod8) be a prime power. Define a quadruple Paley digraph D_q as follows. The vertices of D_q are the elements of the finite field F_q. Vertex u joins to vertex v by an arc if and only if u-v=x⁴ for some x in F_q. We show that all sufficiently large q, D_q has property Q(n, k).

Date received: February 19, 2001