Abstract:

G is a simple graph with a(G) and k(G), its algebraic and vertex connectivity.This paper finds all the graphs satisfying a(G)=k(G).G=(V,E) is a simple graph of order n with vertex connectivity k(G)≤[n/2],and H is one of G's minimal vertex cut set,then a(G)=k(G) holds if and only if for every u∈H and every v∈V\H, uv∈E.

Key words: algebraic connectivity, vertex connectivity, line graph, Laplace matrix, algebraic connectivity, vertex connectivity, line graph