Master of Science (MSc)
Faculty of Science
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.
Costea, Alexandru, "Computational and Theoretical Aspects of N-E.C. Graphs" (2010). Theses and Dissertations (Comprehensive). 968.