On algebraic connectivity of graphs with at most two points of articulation in each block

Abstract

Let G be a connected graph and let L(G) be its Laplacian matrix. We show that given a graph G with a point of articulation u, and a spanning tree T, there is a way to give weights to the edges of G, so that u is the characteristic vertex and the monotonicity property holds on T. A restricted graph is a graph with a restriction that each block can have at most two points of articulation. We supply the structure of a restricted graph G whose algebraic connectivity is extremized among all restricted graphs with the same blocks as those of G. Further results are supplied when each block of G is complete. A path bundle is a graph that consists of internally vertex disjoint paths of the same length with common end vertices. Results pertaining to extremizing the algebraic connectivity of restricted graphs whose blocks are path bundles are supplied. As an application, a comparison of the algebraic connectivities of the sunflower graphs is provided.