Analysis of Complex Networks

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 K₁, K₂, K_2,1, and K_3,1 [126].

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

For any graph, E ≥ .

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

The inequality E(G) + E() ≥ 2n is satisfied by all n-vertex graphs, _n ≥ 5, except by K_n and K_n – e [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) ≤ E₀, where

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