A Nonlinear Optimization Problem to Find Graphs with Maximum Energy

Ahmadi, Sara; Shirdel, Gholam Hassan

doi:10.22034/jmor.2024.721345

A Nonlinear Optimization Problem to Find Graphs with Maximum Energy

Document Type : Original Article

Authors

Sara Ahmadi

Gholam Hassan Shirdel

Department of Mathematics, Faculty of Sciences, University of Qom, Qom, Iran

10.22034/jmor.2024.721345

Abstract

The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of the eigenvalues of the adjacency matrix of graph G. Until now, researchers have not been able to provide a formula for the energy of a graph in terms of graph parameters such as the number of vertices or the number of edges. Therefore, they focused on upper and lower bounds. Over the last 30 years, there has been much interest in this area, leading to the development of many new bounds. The optimal lower bound was introduced, and it was shown that star graphs have the lowest energy of all graphs without an isolated vertex. However, attempts to determine the smallest upper bound have been unsuccessful. In this paper, we take an alternative perspective, focusing on optimization, and present a nonlinear optimization problem to determine the smallest upper bound for the graph energy.

Keywords

Graph energy

Upper bound

Lower bound

Nonlinear optimization