A conjecture on algebraic connectivity of graphs

Let G =(V, E) be a simple graph with vertex set V (G) ={v₁,v₂,..., v_n} and edge set E(G). LetA(G) be the adjacency matrix of graph G and also let D(G) be the diagonal matrix with degrees of the vertices on the main diagonal. The Laplacian matrix of G is L(G) =D(G) − A(G) . Among all eigenvalues of the Laplacian matrix L(G) of a graph G, the most studied is the second smallest, called the algebraic connectivity (a(G)) of a graph G [9]. Let α(G) be the independence number of graph G. Recently, it was conjectured that (see, [1]): a(G)+α(G) is minimum for (Formula presented), where e is any edge in K_{p, q} and p = (Formula presented) (K_{p, q} is a complete bipartite graph). The aim of this paper is to show that this conjecture is true.