Finding counterexamples for a conjecture of Akbari, Alazemi and Andjelić

Abstract

For a graph $G$, its energy $\mathcal{E}(G)$ is the sum of absolute values of the eigenvalues of its adjacency matrix, the matching number $\mu (G)$ is the number of edges in a maximum matching of $G$, while $\Delta$ is the maximum vertex degree of $G$. Akbari, Alazemi and Anđelić in [Appl. Anal. Discrete Math. 15 (2021), 444--459] proved that $\mathcal{E}(G)\le 2\mu (G)$ when $G$ is connected and $\Delta \ge 6$, and conjectured that the same inequality is also valid when $2\le \Delta \le 5$. Here we first computationally enumerate small counterexamples for this conjecture and then provide two infinite families of counterexamples.

arXiv comment32 pages, 7 figures

References in corpus (1)

• Constructions in combinatorics via neural networks