A CONJECTURE ON 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). Let A(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 alpha(G) be the independence number of graph G. Recently, it was conjectured that (see, [1]): a(G) + alpha(G) is minimum for (K-p,K-q\{e}) over bar, where e is any edge in K-p,K- (q) and p = left perpendicularn/2right perpendicular, q = inverted right perpendicularn/2inverted left perpendicular (K-p,K- q is a complete bipartite graph). The aim of this paper is to show that this conjecture is true.