A prolific construction of strongly regular graphs with the n-e.c. property

Peter J. Cameron*, Dudley Stark

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

A graph is n-e.c. (n-existentially closed) if for every pair of subsets U, W of the vertex set V of the graph such that U ∩ W = 0 and |U| + |W| = n, there is a vertex v ∈ V - (U ∪ W) such that all edges between v and U are present and no edges between v and W are present. A graph is strongly regular if it is a regular graph such that the number of vertices mutually adjacent to a pair of vertices v1, v2 ∈ V depends only on whether or not {v1, v2} is an edge in the graph. The only strongly regular graphs that are known to be n-e.c. for large n are the Paley graphs. Recently D. G. Fon-Der-Flaass has found prolific constructions of strongly regular graphs using affine designs. He notes that some of these constructions were also studied by Wallis. By taking the affine designs to be Hadamard designs obtained from Paley tournaments, we use probabilistic methods to show that many non-isomorphic strongly regular n-e.c. graphs of order (q + 1)2 exist whenever q ≥ 16n222n is a prime power such that q ≡ 3 (mod 4).

Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalElectronic Journal of Combinatorics
Volume9
Issue number1 R
Publication statusPublished - 1 Dec 2002

Fingerprint

Dive into the research topics of 'A prolific construction of strongly regular graphs with the n-e.c. property'. Together they form a unique fingerprint.

Cite this