A linear lower bound for the square energy of graphs

Saieed Akbari¹ ; Hitesh Kumar ; Bojan Mohar ; Shivaramakrishna Pragada

¹Sharif University of Technology

The electronic journal of combinatorics, Tome 32 (2025) no. 3

Résumé

Let $G$ be a graph of order $n$ with eigenvalues $\lambda_1 \geq \cdots \geq\lambda_n$. Let \[s^+(G)=\sum_{\lambda_i>0} \lambda_i^2, \qquad s^-(G)=\sum_{\lambda_i<0} \lambda_i^2.\] The smaller value, $s(G)=\min\{s^+(G), s^-(G)\}$ is called the square energy of $G$. In 2016, Elphick, Farber, Goldberg, and Wocjan conjectured that for every connected graph $G$ of order $n$, $s(G)\geq n-1.$ No linear bound for $s(G)$ in terms of $n$ is known. Let $H_1, \ldots, H_k$ be disjoint induced subgraphs of $G$. In this note, we prove that \[s^+(G)\geq\sum_{i=1}^{k} s^+(H_i) \quad \text{ and } \quad s^-(G)\geq\sum_{i=1}^{k} s^-(H_i),\] and then use this result to prove that $s(G)\geq \frac{3n}{4}$ for every connected graph $G$ of order $n\ge 4$.

Détail

DOI : 10.37236/13467

Classification : 05C50, 15A18, 05C15
Mots-clés : chromatic number, disjoint induced subgraphs