Conjectured bounds for the sum of squares of positive eigenvalues of a graph
Preprint
Abstract
A well known upper bound for the spectral radius of a graph, due to Hong, is that $\mu_1^2 \le 2m - n + 1$. It is conjectured that for connected graphs $n - 1 \le s^+ \le 2m - n + 1$, where $s^+$ denotes the sum of the squares of the positive eigenvalues. The conjecture is proved for various classes of graphs, including bipartite, regular, complete $q$-partite, hyper-energetic, and barbell graphs. Various searches have found no counter-examples. The paper concludes with a brief discussion of the apparent difficulties of proving the conjecture in general.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Proof of a conjectured lower bound on the chromatic number of a graphLinear Algebra and its Applications, 2015
- New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency MatrixThe Electronic Journal of Combinatorics, 2013
- Some Inequalities for the Largest Eigenvalue of a GraphCombinatorics, Probability and Computing, 2002
- On graphs with a fixed number of negative eigenvaluesDiscrete Mathematics, 1985
- Lower bounds on the spectra of symmetric matrices with nonnegative entriesLinear Algebra and its Applications, 1985
- Graphs with Exactly Two Negative EigenvaluesMathematische Nachrichten, 1985
- Lower bounds for the clique and the chromatic numbers of a graphDiscrete Applied Mathematics, 1983