ABSTRACT
In this chapter we focus on the eigenvector of the Laplacian matrix corresponding to the algebraic connectivity. This eigenvector is known as a Fiedler vector. In Section 6.1 we investigate the entries of this eigenvector in relationship to the structure of the graph. We study the entries of the Fiedler vector that correspond to cut vertices of the graph and then investigate the entries that correspond to specific blocks of the graph. In a tree, since every edge is a block, we apply the results of Section 6.1 to trees and focus the remainder of this chapter on trees. In Section 6.2 we use the Fiedler vectors of trees to classify trees into two types based on the existence of zero entries in such eigenvectors. This leads us to investigating the inverses of submatrices of the Laplacian matrix obtained by deleting a row and column of the Laplacian matrix corresponding to a specific vertex of the tree, espcially vertices corresponding to a zero entry in the Fiedler vector. These inverses, known as bottleneck matrices, give us useful information about the structure of the tree and also have interesting properties that correspond to the two types of trees. Bottleneck matrices are a vital tool in Section 6.3 when we go on an excursion of studying branches at various vertices of certain unusual trees. Bottleneck matrices continue to be useful in Section 6.4 when we determine which trees of a given fixed diameter have minimum algebraic connectivity. These results help us in Section 6.5 when we consider trees having an edge of infinite weight. In Section 6.6 we generalize the results of this chapter to eigenvectors of Laplacian matrices of trees corresponding to eigenvalues other than the algebraic connectivity. Finally, in Section 6.7 we investigate the (n−1)× (n−1) submatrices of the Laplacian matrix before taking their inverses and observe how the spectral radius of these submatrices corresponding to different vertices varies.
Let G be a connected weighted graph on n vertices labeled 1, . . . , n, with Laplacian matrix L. Then a(G) > 0 by Theroem 4.1.1. In this section, we are interested in the eigenvectors corresponding to the eigenvalue a(G). To this end, we have a definition:
