Parameter Sets for a Class of Strongly Regular Graphs

Abstract

Strongly regular graphs are graphs in which every adjacent pair of vertices share $\lambda$ common neighbours and every non-adjacent pair share $\mu$ common neighbours. We are interested in strongly regular graphs with $\lambda =\mu =k$ such that every such set of $k$ vertices common to any pair always induces a subgraph with a constant number $x$ of edges. The Friendship Theorem proves that there are no such graphs when $\lambda =\mu =1$. We derive constraints which such graphs must satisfy in general, when $\lambda =\mu >1$, and $x\ge 0$, and we find the set of all parameters satisfying the constraints. The result is an infinite, but sparse, collection of parameter sets. The smallest parameter set for which a graph may exist has $4896$ vertices, with $k=1870$.