6 - Graph perturbations

Summary

In this chapter we discuss how the eigenvalues of a graph are affected by small changes in the structure of the graph. In particular we investigate the role of angles and principal eigenvectors in this context. Techniques include both an analytic and an algebraic theory of matrix perturbations applied to the adjacency matrix of a graph.

Introduction

The theory of graph perturbations is concerned primarily with changes in eigenvalues which result from local modifications of a graph such as the addition or deletion of a vertex or edge. For a variety of such modifications, the corresponding characteristic polynomials are discussed in Section 4.3, and in these cases the eigenvalues of the perturbed graph are determined as implicit functions of algebraic and geometric invariants of the original graph. One of the problems investigated in this chapter is that of expressing the perturbed eigenvalues as series in these invariants. For this purpose we apply (in Section 6.3) the classical analytic theory of matrix perturbations to an adjacency matrix: here it is necessary to impose conditions which ensure convergence of the resulting power series, but when these conditions are satisfied we can find simultaneously an eigenvalue and eigenvector of the perturbed graph to any degree of accuracy. Clearly this is related to the second problem of estimating changes in eigenvalues, where we might hope to deal with a wider range of perturbations.