O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 images, the graph consisting of isolated vertices. Its energy is zero.

The minimum-energy n-vertex graph without isolated vertices is the complete bipartite graph Kn–1,1, also known as the star [12]. Its energy is equal to images 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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required