On graphs with algebraic connectivity equal to minimum edge density

Given an undirected graph G = (V, E) and a nonempty subset X subset of V, the edge density of X is given by rho(X) = \V\ \E-X\/\X\ \V\X\, where E-X is the set of all edges with one end in X and the other end in V\X. It is known that the algebraic connectivity of G, denoted by alpha(G), satisfies alpha(G) less than or equal to min(Xsubset of or equal toV) rho(X). In this paper we study the graphs G for which equality holds in the above inequality. (C) 2003 Elsevier Inc. All rights reserved.