Energy and independence number

Abstract

For a graph $G$ of order $n$, with adjacency eigenvalues $λ_1(G) \geq \cdots \geq λ_n(G)$, the \emph{energy} of $G$ is defined to be \[\mathcal{E}(G)=\sum_{i=1}^{n} |λ_i(G)|.\] A well-known conjecture from the 1980s by Fajtlowicz states that for any graph $G$, \[\mathcal{E}(G) \ge 2\left(n-α(G)\right),\] where $α(G)$ denotes the independence number. We prove this conjecture.

Disclosure

“AI statement We acknowledge the use of AI tools during the ideation phase. We declare that the text is not AI-generated. References [1] Aida Abiad, Gabriel Coutinho, Emanuel Juliano, and Luuk Reijnders. A graph energy con- jecture through the lenses of semidefinite programming,”

PDF page 7

Classification

Code generation, completion, or debugging

Multiplier

2

Verified

2026-08-23T19:02:16.628896Z

Structural counts