Analysis of Complex Networks

7.4 Graphs Extremal with Regard to Energy

One of the fundamental questions that is encountered in the study of graph energy is which graphs (from a given class) have the greatest and smallest E-values. The first such result was obtained for trees [74], when it was demonstrated that the star has minimum and the path maximum energy. In the meantime, a remarkably large number of papers were published on such extremal problems: for general graphs [13, 14, 16, 75–78], trees and chemical trees [79–93], unicyclic [94–107], bicyclic [108–114], tricyclic [115, 116], and tetracyclic graphs [117], as well as for benzenoid and related polycyclic systems [118–122].

In this section we state a few of these results, selecting those that can be formulated in a simple manner.

We first present elementary results.

The n-vertex graph with minimum energy is , the graph consisting of isolated vertices. Its energy is zero.

The minimum-energy n-vertex graph without isolated vertices is the complete bipartite graph K_n–1,1, also known as the star [12]. Its energy is equal to cf. Theorem 7.2.

Finding the maximum-energy n-vertex graph(s) is a much more difficult task, and a complete solution of this problem is not known. For some results along these lines see Theorem 7.5.

Let G be a graph on n vertices and