Abstract:
We study graphs in which $\lambda(a,b)=\lambda_1,\lambda_2$ for every edge $\{a,b\}$ and all $\mu$-subgraphs are 2-cocliques. We give a description of connected edge-regular graphs for $k\geqslant(b_1^2+3b_1-4)/2$. In particular, the following examples confirm that the inequality $k>b_1(b_1+3)/2$ is a sharp bound for strong regularity: the $n$-gon, the icosahedron graph, the graph in $\operatorname{MP}(6)$ and the distance-regular graph of diameter 4 with intersection massive $\{x,x-1,4,1;1,2,x-1,x\}$, which is an antipodal 3-covering of the strongly regular graph with parameters $((x+2)(x+3)/6,x,0,6)$.