Graphs with prescribed adjacency properties

Abstract

A graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices 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. The class of graphs having property P(m.n,k) is denoted by ζ(m,n,k). The problem that arises is that of characterizing the class ζ(m,n,k). One particularly interesting problem that arises concerns the functionP(m,n,k) = min{υ(G) : G є ζ(m,n,k) }.In Chapter 2, we establish some important properties of graphs in the class ζ(m,n,k) and a lower bound on p(m,n,k). In particular, we prove thatp(n,n,k) ≥ 4n-1 (2(n+k) + ½ (3 = (-1)n+k+1} + 1/3 l 1/3One of the results in Chapter 2 is that almost all graphs have property P(m,n,k). However, few members of ζ(m,n,k) have been exhibited. In Chapter 3. we construct classes of graphs having property P(l,n,k) . These classes include the cubes, "generalized" Petersen graphs and "generalized" Hoffman-Singleton graphs.An important graph in the study of the class ζ(m,n,k) is the Paley graph Gq defined as follows. Let q = l(mod 4) be a prime power. The vertices of Gq are the elements of the finite field IFq. Two vertices a and b are joined by an edge if and only if their difference is a quadratic residue, that is a - b = y2 for some y є IFq. In chapter 4, we prove that for a prime p = l(mod 4), all sufficiently large Paley graphs GP satisfy property P(m.n,k). This is established by making use of results from prime number theory.In Chapter 5 , we establish, by making use of results from finite fields, the adjacency properties of Paley graphs of order q = pd , with p a prime.For directed graphs, there is an analogue of the above adjacency property concerning tournaments. A tournament Tq of order q is said to have property Q(n,k) if every subset of n vertices of Tq is dominated (if there is an arc directed from a vertex u to a vertex v, we say that u dominates v and that v is dominated by u) by at least k other vertices.Let q = 3(mod 4) is a prime power. The Paley tournament Dq is defined as follows. The vertices of Dq are the elements of the finite field IFq. Vertex a is ioined to vertex b by an arc if and only if a - b is a quadratic residue in Fq. In Chapter 6, we prove that the Paley tournament Dq has property Q(n,k) wheneverq > {(n - 3)2n-1 + Z}G + kZn - 1. A graph G is said to have property P*(rn,n,k) if for any set of rn + n distinct vertices of G there are exactly 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 class of graphs having property P*(m.n,k) is denoted by S*(m,n.k). The class S*(m,n,k) has been studied when one of m or n is zero. In Chapter 7, we show that, for m = n = 1, graphs with this property (k + t)' + 1, are the strongly regular graphs with parameters ( k + t,t - 1,t) for some positive integer t. For rn 2 1, n 2 1, and m + n 2 3, we show that, there is no graph having property P*(m.n,k), for any positive integer k. The first Chapter of this thesis provides the motivation, terminology. general concepts and the problems concerning the adjacency properties of graphs. In Chapter 8 . we present some open problems.