Energy and independence number

2026/07/22 by Hitesh Kumar, Shivaramakrishna Pragada
#math.CO

paper · pdf

Abstract

For a graph G of order n, with adjacency eigenvalues λ₁(G) ≥ ⋯ ≥ λ_n(G), the energy of G is defined to be E(G)=∑_i=1ⁿ |λ_i(G)|. A well-known conjecture from the 1980s by Fajtlowicz states that for any graph G, E(G) ≥ 2(n-α(G)), where α(G) denotes the independence number. We prove this conjecture.

Related

• A graph energy conjecture through the lenses of semidefinite programming
• Graph energy estimates via the Chebyshev functional
• A lower bound of the energy of non-singular graphs in terms of average degree
• Choice Number and Energy of Graphs
• What is the meaning of the graph energy after all?