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

Let KnK_n be the complete graph on nn vertices, and let HH be a subgraph of KnK_n with E(H)n3|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 n3n-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 n7n\leq 7 and give the conjectured threshold for guaranteeing a two-eigenvalue matrix realization after deleting edges from a complete graph.

Sources & referencesView supporting material

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.