×

Hadamard matrices and strongly regular graphs with the 3-e. c. adjacency property. (English) Zbl 0955.05068

Summary: A graph is \(3\)-e.c. if for every \(3\)-element subset \(S\) of the vertices, and for every subset \(T\) of \(S\), there is a vertex not in \(S\) which is joined to every vertex in \(T\) and to no vertex in \(S\setminus T\). Although almost all graphs are \(3\)-e.c., the only known examples of strongly regular \(3\)-e.c. graphs are Paley graphs with at least \(29\) vertices. We construct a new infinite family of \(3\)-e.c. graphs, based on certain Hadamard matrices, that are strongly regular but not Paley graphs. Specifically, we show that Bush-type Hadamard matrices of order \(16n^2\) give rise to strongly regular \(3\)-e.c. graphs, for each odd \(n\) for which \(4n\) is the order of a Hadamard matrix.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05E30 Association schemes, strongly regular graphs