Proof of conjecture involving algebraic connectivity and average degree of graphs

Let G be a simple connected graph of order n with m edges. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the Laplacian matrix of graph G is L(G)=D(G)−A(G). Among all eigenvalues of the Laplacian matrix L(G) of graph G, the most studied is the second smallest, called the algebraic connectivity a(G) of a graph. Let d‾(G) and δ(G) be the average degree and the minimum degree of graph G, respectively. In this paper we characterize all graphs for which (i) a(G)=1 with δ(G)≥⌈[Formula presented]⌉, and (ii) a(G)=2 with δ(G)≥[Formula presented]. In [1], Aouchiche mentioned a conjecture involving the algebraic connectivity a(G) and the average degree d‾(G) of graph G: a(G)−d‾(G)≥4−n−[Formula presented] with equality holding if and only if G‾≅K_1,n−2∪K₁ (K_1,n−2 is a star of order n−1 and G‾ is the complement of graph G). Here we prove this conjecture.