ABSTRACT
Probably the most important property of a graph that we can obtain from the Laplacian matrix is its algebraic connectivity. The algebraic connectivity of a graph is simply the second smallest eigenvalue of the Laplacian matrix. We learned in Chapter 1 that if we add a positive semidefinite matrix to an existing positive semidefinite matrix, the eigenvalues will monotonically increase. Since adding edges to an existing graph results in a Laplacian matrix obtained by adding a positive semidefinite matrix to the existing Laplacian matrix, we saw from Theorem 4.1.2 that the second smallest eigenvalue (in fact all eigenvalues) monotonically increases. Moreover, in light of Theorem 4.1.1, the second smallest eigenvalue of the Laplacian matrix is positive if and only if the graph is connected, and is zero otherwise. Hence the second smallest eigenvalue of the Laplacian matrix is a useful way of measuring the connectivity of the graph. Section 5.1 gives us an introduction to the algebraic connectivity of a graph. Here, we learn which graphs have maximum and minimum algebraic connectivity, and also develop an upper bound on the algebraic connectivity in terms of the vertex connectivity of a graph. Recalling that adding an edge to a graph causes the algebraic connectivity to monotonically increase, this motivates us to explore the effects that varying the edge weight has on the algebraic connectivity. This we do in Section 5.2 where we learn that increasing the weight of an edge causes the algebraic connectivity to increase in a concave downward fashion. In Section 5.3 we develop upper and lower bounds on the algebraic connectivity of graphs in terms of a graph’s diameter and mean distance. Since graphs with large diameter and mean distance tend to have less edges, they are “less connected” and thus have lower algebraic connectivity. Section 5.4 focuses on using the edge density of a graph to give an upper bound on its algebraic connectivity. This leads us to the concept the isoperimetric number of a graph which is helpful to us in determing upper bounds on the algebraic connectivity in terms of the graph’s topological properties. Section 5.5 focuses on planar graphs while Section 5.6 focuses on graphs of higher genus.
