The edge-deletion conjecture for two-eigenvalue realizations of complete graphs

About 3 years old · traced to

Let KnK_n be the complete graph on nn vertices, and let HH be a subgraph of KnK_n with ∣E(H)∣≤n−3|E(H)|\leq n-3. Write Kn\HK_n\backslash H for the graph obtained by removing the edges of HH from KnK_n. Edge-deletion conjecture. Removing up to n−3n-3 edges from KnK_n does not change its number of distinct eigenvalues; explicitly, for every such HH,

q(Kn\H)=2.q(K_n\backslash H)=2.

This would extend the equality known for n≤7n\leq 7 and give the conjectured threshold for guaranteeing a two-eigenvalue matrix realization after deleting edges from a complete graph.

References

Primary source

Shaun Fallat and Seyed Ahmad Mojallal, “Spectral Applications of Vertex-Clique Incidence Matrices Associated with a Graph”, arXiv:2307.09663 (2023).

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.