pith. sign in

arxiv: 1807.06436 · v1 · pith:7HA4PRJHnew · submitted 2018-07-17 · 🧮 math.SP · math.CO

A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph

classification 🧮 math.SP math.CO
keywords conjecturegraphsgraphdistincteigenvaluesminimumnordhaus-gaddumnumber
0
0 comments X
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.