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

We state here a few noteworthy results on graph energy that did not fit into the previous sections.

E(G) ≥ 4 holds for all connected graphs, except for K1, K2, K2,1, and K3,1 [126].

The rank images of a graph is the rank of its adjacency matrix. For a connected bipartite graph G of rank images [126],

images

For any graph, Eimages.

Let χ(G) be the chromatic number of graph G. For any n-vertex graph G, E(G) ≥ 2(n – χ(images)) [126].

The inequality E(G) + E(images) ≥ 2n is satisfied by all n-vertex graphs, n ≥ 5, except by Kn and Kne [126].

As an immediate special case of the Koolen–Moulton upper bound (7.2), for an n-vertex regular graph of degree r, we have E(G) ≤ E0, where

images

Balakrishnan [59] showed that for any ε > 0, there exist infinitely many n, for which there are n-vertex regular graphs of degree ...

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