Analysis of Complex Networks

7.3 Hyperenergetic, Hypoenergetic, and Equienergetic Graphs

7.3.1 Hyperenergetic Graphs

The energy of the n-vertex complete graph K_n 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 K_n 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 K_n, n ≥ 5, and of K_{n/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 ...