Modifying graphs to bound the number of distinct eigenvalues

DOI10.1016/J.TCS.2026.116168MaRDI QIDQ7347255zbMATH OpenFDO

Authors Neeldhara Misra, Harshil Mittal, Saket Saurabh, Dhara Thakkar

Publication date 14 September 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.116168

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of computing (68Qxx) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cites work

• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Computing all or some eigenvalues of symmetric \(\mathcal{H}_{\ell}\)-matrices
• Geometric versions of the three-dimensional assignment problem under general norms
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1496857 (Why is no real title available?)
• Large independent sets in triangle-free cubic graphs: beyond planarity
• On characterizing certain graphs with four eigenvalues by their spectra
• On split graphs with four distinct eigenvalues
• Parameterized algorithms
• Paths, Trees, and Flowers
• Reducing rank of the adjacency matrix by graph modification

This page was built for publication: Modifying graphs to bound the number of distinct eigenvalues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7347255)