A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
classification
🧮 math.SP
math.CO
keywords
conjecturegraphsgraphdistincteigenvaluesminimumnordhaus-gaddumnumber
read the original abstract
We propose a Nordhaus-Gaddum conjecture for $q(G)$, the minimum number of distinct eigenvalues of a symmetric matrix corresponding to a graph $G$: for every graph $G$ excluding four exceptions, we conjecture that $q(G)+q(G^c)\le |G|+2$, where $G^c$ is the complement of $G$. We compute $q(G^c)$ for all trees and all graphs $G$ with $q(G)=|G|-1$, and hence we verify the conjecture for trees, unicyclic graphs, graphs with $q(G)\le 4$, and for graphs with $|G|\le 7$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.