Document Type

Thesis

Degree Name

Master of Science (MSc)

Department

Mathematics

Faculty/School

Faculty of Science

First Advisor

Anthony Bonato

Advisor Role

Thesis Supervisor

Abstract

We consider graphs with the n-existentially closed adjacency property. For a positive integer n, a graph is n-existentially closed (or n-e.c.) if for all disjoint sets of vertices A and B with \A∪ B\ = n (one of A or B can be empty), there is a vertex 2 not in A∪B joined to each vertex of A and no vertex of B. Although the n-e.c. property is straightforward to define, it is not obvious from the definition that graphs with the property exist. In 1963, Erdos and Rényi gave a non-explicit, randomized construction of such graphs. Until recently, only a few explicit families of n-e.c. graphs were known such as Paley graphs. Furthermore, n-e.c. graphs of minimum order have received much attention due to Erdos’ conjecture 011 the asymptotic order of these graphs. The exact minimum orders are only known for n = 1 and n = 2.

We provide a survey of properties and examples of n-e.c. graphs. Using a computer search, a new example of a 3-e.c. graph of order 30 is presented. Previously, no known 3-e.c. graph was known to exist of that order. We give a new randomized construction of n-e.c. vertex-transitive graphs, exploiting Cayley graphs. The construction uses only elementary probability and group theory.

Convocation Year

2010

Download

Included in

Mathematics Commons

Share

COinS