Proof of conjectures involving algebraic connectivity of graphs

Let G = (V, E) be a simple graph with vertex set V(G) = (v(1), v(2),..., v(n)) and edge set E(G). The Laplacian matrix of G is L(G) = D(G) - A(G), where D(G) is the diagonal matrix of its vertex degrees and A (G) is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity (a(G)) of a graph [18]. In this paper we give a lower bound on the algebraic connectivity of graphs. Moreover, we mention two conjectures, obtained by the system AutoGraphiX, about the algebraic connectivity (a(G)), diameter (D) and the minimum degree (8) of graphs (see, [2], available online at http://www.gerad.ca/similar to agx/): (i) a(G) + D >= 3 with equality if and only if G is isomorphic to a graph with D = 2 and a(G) = 1, and (ii) a(G) 8 is minimum for a graph composed of 2 cliques on [n/2] vertices with a common vertex if n is odd, and linked by an edge if n is even. Here we prove conjecture in (i) using the lower bound on the algebraic connectivity of graphs and conjecture in (ii), respectively. (C) 2013 Elsevier Inc. All rights reserved.