#### 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.

#### Recommended Citation

Costea, Alexandru, "Computational and Theoretical Aspects of *N*-E.C. Graphs" (2010). *Theses and Dissertations (Comprehensive)*. 968.

http://scholars.wlu.ca/etd/968

#### Convocation Year

2010