Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: A prolific construction of strongly regular graphs with the . property. | A prolific construction of strongly regular graphs with the . property Peter J. Cameron and Dudley Stark School of Mathematical Sciences Queen Mary University of London Mile End Road London E1 4NS . Submitted October 18 2001 Accepted July 19 2002. Abstract A graph is . n-existentially closed if for every pair of subsets U W of the vertex set V of the graph such that U n W and UI IWI n there is a vertex V 2 V U 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 2 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 . 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 . graphs of order q 1 2 exist whenever q 16n222n is a prime power such that q 3 mod 4 . 1 Introduction The vertex set of a graph G will be denoted by V V G and the edge set by E E G . The number of vertices is denoted by N V . We dehne a graph to be . n-existentially closed if for every pair of subsets U W of the vertex set V such that U n W and UI WI n there is a vertex v 2 V U u W such that all edges between v and U are present and no edges between v and W are present. A strongly regular SR N K Ả M graph is a regular graph such that the number of vertices adjacent to a pair of vertices v1 v2 2 V depends only on whether or not v1 v2 2 E. Denote the common degree of the vertices of G by K. Given v 2 V let THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 R31 1 r v w G V w v G E
