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.

Keywords:

• Laplacian matrix
• Fiedler vector
• algebraic connectivity
• block
• block graph
• path bundle
• sunflower graph

AMS Subject Classifications::

• 05C50
• 05C05
• 15A18

Acknowledgements

We thank the referees for their meticulous observations and suggestions which helped immensely in improving this article. R.B. Bapat acknowledges the support of the JC Bose Fellowship, Department of Science and Technology, Government of India. A.K. Lal and S. Pati take this opportunity to thank the Indian Statistical Institute Delhi for their hospitality from 16 July 2010 to 23 July 2010.