ABSTRACT
In the beginning of Chapter 7, we briefly used the group inverse of the Laplacian matrix of a graph in order to create bottleneck matrices. In this chapter, we investigate the group inverse of the Laplacian matrix much more deeply and study the combinatorial aspects behind its construction. In Section 8.1, we show how the structure of a tree can be used to construct the group inverse of the Laplacian matrix. Distances between pairs of vertices in a weighted tree will be significant in our construction of such matrices. We then use the group inverse in Section 8.2 to derive a lower bound on the algebraic connectivity of graphs. We also show when equality can occur between this lower bound and the algebraic connectivity. We then return our focus to trees in Section 8.3 and investigate which vertices of trees contribute to this lower bound. Finally, in Section 8.4 we refine our results from Section 5.2 concerning how varying the weight of the edges of a graph affects the algebraic connectivity. The group inverse turns out to be very useful in this endeavor.
