Tan et al.'s conjecture on co-edge-regular graphs with four eigenvalues

About 1 year old · traced to

Let GG be a connected kk-regular graph with nn vertices and co-edge-regular with parameter μ\mu, having four distinct eigenvalues. Let t≥2t\geq 2 be an integer. Tan et al.'s conjecture. There exists a constant ntn_t such that, if θmin⁡(G)≥−t\theta_{\min}(G)\geq -t, n≥ntn\geq n_t and k<n−2−(t−1)24k<n-2-\frac{(t-1)^2}{4}, then either GG is the ss-clique extension of a strongly regular graph for 2≤s≤t−12\leq s\leq t-1, or GG is a p×qp\times q-grid with p>q≥2p>q\geq 2. The conjecture seeks a Neumaier-type classification for co-edge-regular graphs with four distinct eigenvalues; the cited spectral characterizations of clique extensions motivate it, but no resolution is supplied here.

References

Primary source

Hong-Jun Ge and Jack H. Koolen, “On co-edge-regular graphs with 4 distinct eigenvalues”, arXiv:2503.12025 (2025).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.