Analysis of Complex Networks

7.2 Bounds for the Energy of Graphs

Let G be a graph possessing n vertices and m edges. We say that G is an (n, m)-graph.

For any (n, m)-graph [1], = 2m.

In what follows we assume that the graph eigenvalues are labeled in a nonincreasing manner, i.e., that

If G is connected, then λ₁ > λ₂ [1]. Because λ₁ ≥ |λ_i|, i = 2,..., n, the eigenvalue λ₁ is referred to as the spectral radius of graph G.

Some of the simplest and longest standing [8] bounds for the energy of graphs are given below.

Theorem 7.1 [11] For an (n, m)-graph G,

with equality if and only if G is either an empty graph (with m = 0, i.e., )or a regular graph of degree 1, i.e., .

Theorem 7.2 [12] For a graph G with m edges,

Equality E (G) = holds if and only if G consists of a complete bipartite graph K _a,b, such that a· b = m, and ...