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], images = 2m.

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

images

If G is connected, then λ1 > λ2 [1]. Because λ1 ≥ |λi|, i = 2,..., n, the eigenvalue λ1 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,

images

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

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

images

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

Get Analysis of Complex Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.