Coefficient of ergodicity type bounds for the algebraic connectivity of graphs.

摘要

Traditionally, a graph G on n vertices is represented using the n x n adjacency matrix. In this dissertation, we represent a graph using a variation of the adjacency matrix known as the Laplacian matrix. The Laplacian matrix has many interesting properties. Foremost, the Laplacian matrix is singular and positive semidefinite and so its eigenvalues are nonnegative numbers which can therefore be arranged in nondescending order with zero being the smallest. Here, we research the properties of the second smallest eigenvalue of the Laplacian matrix. This eigenvalue measures the connectedness of the graph and is therefore referred to as the algebraic connectivity of G . It is known that the algebraic connectivity of a graph is strictly positive if and only if the graph is connected. In this dissertation, lower bounds for the algebraic connectivity of many types of graphs are developed using the group inverse of the Laplacian matrix and using an upper bound for the nontrivial eigenvalues of a matrix with constant row sums, which is similar to the coefficient of ergodicity used in probability.