Conjecture on large co-edge-regular graphs with four eigenvalues

From papers

Let Γ\Gamma be a connected co-edge-regular graph with four distinct eigenvalues. Let t2t\geq 2 be an integer and write V(Γ)=n(Γ)|V(\Gamma)|=n(\Gamma). An ss-clique extension is a graph obtained from a graph by replacing each vertex with a clique of size ss, with adjacency between cliques determined by adjacency of the corresponding original vertices. Large co-edge-regular graph conjecture. There exists a constant ntn_t such that, if

θmin(Γ)tandn(Γ)nt,\theta_{\min}(\Gamma)\geq -t \quad\text{and}\quad n(\Gamma)\geq n_t,

then Γ\Gamma is the ss-clique extension of a strongly regular graph for some integer ss satisfying 2st12\leq s\leq t-1. This predicts a structural classification of sufficiently large connected co-edge-regular graphs in this spectral range; the source presents it as a belief motivated by the study of regular graphs with four distinct eigenvalues and gives no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Sakander Hayat, Jack H. Koolen and Muhammad Riaz, “A spectral characterization of the s-clique extension of the square grid graphs”, arXiv:1806.03593 (2018).

Solutions 0

No solutions have been posted yet.