ABSTRACT
In the previous chapter we investigated the bottleneck matrices for trees. In this chapter we generalize this concept to graphs which are not trees. We provide a brief review of the group inverse of a matrix in Section 7.1 and discuss how bottleneck matrices for graphs are constructed. We then apply these ideas in Section 7.2 to show how the Perron components at cut vertices of a graph can be used to compute its algebraic connectivity. In this section, we generalize much of Section 6.2. In Sections 7.3 and 7.4 we use bottleneck matrices for graphs to show which graphs of fixed girth have the minimum and maximum algebraic connectivities. We see in Section 7.3 that the graphs which have the minimum algebraic connectivity are certain unicyclic graphs. Therefore in Section 7.4 we focus on determining the unicyclic graphs of fixed girth that yield the maximum algebraic connectivity. Since unicyclic graphs closely resemble trees, we will combine ideas from both this chapter and Chapter 6 in order to prove our results. In Section 7.5 we apply the idea of bottleneck matrices to find an upper bound on the algebraic connectivity of a graph in terms of the number of cut vertices. Recall from Section 5.1 that the maximum algebraic connectivity of a graph with a cut vertex is one. In this Section 7.5 we will refine these results. Finally in Section 7.6 we generalize the results of Section 6.7 by investigating the spectral radius of submatrices of the Laplacian matrices of graphs created by deleting a row and column corresponding to a vertex of the graph. As in Chapter 6, taking the inverse of these matrices yields bottleneck matrices. Hence we compare the results concerning these submatrices to those of bottleneck matrices.
