O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 v1, v2,..., vn. 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 vi and vj are adjacent and equal to zero otherwise.

The eigenvalues λ1, λ2,..., λ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(λ InA(G)), where In 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 λ1, λ2,..., λ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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required