Graphs with prescribed adjacency properties
Access Status
Authors
Date
1993Supervisor
Type
Award
Metadata
Show full item recordSchool
Collection
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) ≥ 4n1 (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" HoffmanSingleton 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)2n1 + 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.
Related items
Showing items related by title, author, creator and subject.

Lam, Bee K. (1999)A network is a system that involves movement or flow of some commodities such as goods and services. In fact any structure that is in the form of a system of components some of which interact can be considered as a network. ...

Ananchuen, Watcharaphong; Caccetta, Louis (2006)A graph G is nexistentially closed or ne.c. if for any two disjoint subsets A and B of vertices of G with A ∪ B = n, there is a vertex u /∈A ∪ B that is adjacent to every vertex of A but not adjacent to any vertex of ...

Ananchuen, Nawarat (1994)Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n  1, G is said to be kextendable if for every matching M of size k in G there is a perfect matching in G containing all the edges ...