Papers › A combinatorial bound on the number of distinct eigenvalues of a graph
A combinatorial bound on the number of distinct eigenvalues of a graph
Sarah Allred, Craig Erickson, Kevin Grace, H. Tracy Hall, Alathea Jensen
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The smallest possible number of distinct eigenvalues of a graph G, denoted by q(G), has a combinatorial bound in terms of unique shortest paths in the graph. In particular, q(G) is bounded below by k, where k is the number of vertices of a unique shortest path joining any pair of vertices in G. Thus, if n is the number of vertices of G, then n-q(G) is bounded above by the size of the complement (with respect to the vertex set of G) of the vertex set of the longest unique shortest path joining any pair of vertices of G. The purpose of this paper is to commence the study of the minor-monotone floor of n-k, which is the minimum of n-k among all graphs of which G is a minor. Accordingly, we prove some results about this minor-monotone floor.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections