Conjectures on index and algebraic connectivity of graphs

Let G=(V,E) be a simple graph with vertex set V={v1,v2,…,vn} and edge set E(G). The adjacency matrix of a graph G is denoted by A(G) and defined as the n×n matrix (aij), where aij=1 for vivj∈E(G) and 0 otherwise. The largest eigenvalue (λ1) of A(G) is called the spectral radius or the index of 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) of a graph [12]. In [1,2], Aouchiche et al. have given a series of conjectures on index (λ1) and algebraic connectivity (a) of G (see also [3]). Here we prove two conjectures and disprove one by a counter example.