Handbook of Linear Algebra, 2nd Edition

Chapter 48

Algebraic Connectivity

Steve Kirkland

National University of Ireland Maynooth

48.1 Algebraic Connectivity for Simple Graphs: Basic Theory

Let G be a simple graph on n ≥ 2 vertices with Laplacian matrix LG, and label the eigenvalues of LG as 0 = μ1 ≤ μ2 ≤ ... ≤ μn. Throughout this chapter, we consider only Laplacian matrices for graphs on at least two vertices. Henceforth, we use the term graph to refer to a simple graph.

Definitions:

The algebraic connectivity of G, denoted α(G), is given by α(G) = μ2.

A Fiedler vector is an eigenvector of LG corresponding to α(G).

The support of a vector is the collection of indices corresponding to its nonzero entries.

Given graphs G1 = (V1, E1) and G2 = (V2, E2), their Cartesian product, G1 ×