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.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 ...

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