Energy of Graphs

Introduction

The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. It has a correlation with the total π-electron energy of a molecule in the quantum chemistry as calculated with the Huckel molecular orbital method (Gutman & Polansky, 1986).

Let G be a finite, simple, undirected graph with vertex set V(G) and edge set F(G) The number of vertices of G is denoted by n and the number of edges of G is denoted by m. If V(G) = {v₁, v₂, ..., v_n} then the adjacency matrix of G is a square matrix A(G) = [a_ij] of order n in which a_ij = 1, if the vertex v_i is adjacent to the vertex v_j and a_ij = 0, otherwise. The characteristic polynomial of A(G) denoted by Φ(G: λ) = det(λI – A(G)), where I is an identity matrix of order n. The roots of the equation Φ(G: λ) = 0 are called the eigenvalues of G and they are labeled as λ₁, λ₂, ..., λ_n. Their collection is called the spectrum of G denoted by Spec(G) (Cvetkovic, Doob & Sachs, 1980).

If λ₁, λ₂, ..., λ_k are the distinct eigenvalues with respective multiplicities m₁, m₂, …, m_k then we write Spec(G) = . Since A(G) is a real symmetric matrix, its eigenvalues are real and can be ordered as λ₁ ≥ λ₂ ≥ ... ≥ λ_n.

Two non-isomorphic graphs are said to be cospectral if they have same spectra. Details about the graph spectra can be found in the book (Cvetkovic, Doob & Sachs, 1980) and for graph theoretic terminology one can refer the book (Harary, 1999).

One of the chemical applications of spectral graph theory is based on the correspondence between the graph eigenvalues and the molecular orbital energy level of π-electron in conjugated hydrocarbons (Gutman & Polansky, 1986).

The molecular graph of a hydrocarbon is obtained as follows: the carbon atoms are represented by the vertices and two vertices are adjacent if and only if there is a carbon-carbon bond. Hydrogen atoms are ignored.

Figure 1.

Molecule and its molecular graph

Within the Huckel molecular orbital (HMO) method (Huckel & Quantentheoretische Beitrage zum Benzolproblem, 1931), the energy level of π-electron in molecules of conjugated hydrocarbons are related to the eigenvalues of a molecular graph as ε_i = α + β_i where α and β are empirical constants of the HMO model. The total energy of π-electrons denoted by E_π is