Analysis of Complex Networks

7.1 Introduction

In this chapter we are concerned with the eigenvalues of graphs and some of their chemical applications. Let G be a (simple) graph, with vertex set V(G) and edge set E(G). The number of vertices of G is n, and its vertices are labeled by v₁, v₂,..., v_n. The adjacency matrix A(G) of the graph G is a square matrix of order n, whose (i, j)-entry is equal to 1 if the vertices v_i and v_j are adjacent and equal to zero otherwise.

The eigenvalues λ₁, λ₂,..., λ_n of the adjacency matrix A(G) are said to be the eigenvalues of the graph G and to form its spectrum. Details of the spectral theory of graphs can be found in the seminal monograph [1].

The characteristic polynomial of the adjacency matrix, i.e., det(λ I_n– A(G)), where I_n is the unit matrix of order n, is said to be the characteristic polynomial of the graph G and will be denoted by ϕ(G, λ). From linear algebra it is known that the graph eigenvalues are just the solutions of the equation ϕ(G, λ) = 0.

One of the most remarkable chemical applications of graph theory is based on the close correspondence between the graph eigenvalues and the molecular orbital energy levels of π-electrons in conjugated hydrocarbons. For details, see [2–4]. If G is a molecular graph of a conjugated hydrocarbon with n vertices and λ₁, λ₂,..., λ_n are its eigenvalues, then in the so-called Hüchkel molecular orbital (HMO) approximation [3,5], the energy of the ith molecular orbital is given by

where α and β are pertinent constants. In order ...