“Graph Perturbations”

Summary

INTRODUCTION

The topic of graph perturbations is, like the classical perturbation theory of linear operators [29], concerned primarily with changes in eigenvalues which result from various perturbations. The eigenvalues are those of an adjacency matrix of a graph G, and a perturbation of G is to be thought of as a local modification such as the addition or deletion of a vertex or edge. Here G is a finite undirected graph without loops or multiple edges, and if its vertices are labelled 1,2,…,n then the corresponding adjacency matrix A is (a_ij) where a_ij = 1 if vertices i and j are adjacent, and a_ij = 0 otherwise. The matrix A is regarded as a matrix with real entries, and since A is symmetric, its eigenvalues are real. These eigenvalues are independent of the ordering of the vertices of G, and so we refer to them as the eigenvalues of G. The n eigenvalues together comprise the spectrum of G.

We shall be concerned with three related questions: (1) What algebraic information about G is sufficient to determine the eigenvalues of a given perturbation of G? (2) Does a given eigenvalue increase or decrease under a given perturbation? (3) How can we compare the effects on eigenvalues oi two different perturbations? Such questions were raised in 1979 by Li and Feng [31] in relation to the largest eigenvalue of a graph, and in effect they considered graphs perturbed by the relocation of certain pendant edges.