7.3 Hyperenergetic, Hypoenergetic, and Equienergetic Graphs

7.3.1 Hyperenergetic Graphs

The energy of the n-vertex complete graph Kn is equal to 2(n–1). We call an n-vertex graph G hyperenergetic if E(G) > 2(n–1). From Nikiforov's Theorem 7.24 we see that almost all graphs are hyperenergetic. Therefore, any search for hyperenergetic graphs appears nowadays a futile task. Yet, before Theorem 7.24 was discovered, a number of such results were obtained. We outline here some of them.

In [7] it was conjectured that the complete graph Kn had greatest energy among all n-vertex graphs. This conjecture was soon shown to be false [44].

The first systematic construction of hyperenergetic graphs was proposed by Walikar, Ramane, and Hampiholi [45], who showed that the line graphs of Kn, n ≥ 5, and of Kn/2, n/2, n ≥ 8, are hyperenergetic. These results were eventually extended to other graphs with a large number of edges [46, 47].

Hou and Gutman [48] showed that the line graph of any (n, m)-graph, n ≥ 5, m ≥ 2n, is hyperenergetic. Also, the line graph of any bipartite (n, m)-graph, n ≥ 7, m ≥ 2(n – 1), is hyperenergetic. Some classes of circulant graphs [49–51] as well as Kneser graphs and their complements [52] are hyperenergetic. In fact, almost all circulant graphs are hyperenergetic [49].

Graphs on n vertices with fewer than 2n – 1 edges are not hyperenergetic [53, 54]. This, in particular, implies that Hückel graphs (graphs representing conjugated molecules [2–4], in which the vertex degrees ...

Get Analysis of Complex Networks now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.