Graphs with given diameter maximizing the algebraic connectivity

AbstractWe propose a class of graphs GD∗(n1,n2,…,nD+1), containing of a chain of D+1 cliques Kn1,Kn2,…,KnD+1, where neighboring cliques are fully-interconnected. The class of graphs has diameter D and size N=∑1⩽i⩽D+1ni. We prove that this class of graphs can achieve the maximal number of links, the minimum average hopcount, and more interestingly, the maximal of any Laplacian eigenvalue among all graphs with N nodes and diameter D. The algebraic connectivity is the eigenvalue of the Laplacian that has been studied most, because it features many interesting properties. We determine the graph with the largest algebraic connectivity among graphs with N nodes and diameter D⩽4. For other diameters, numerically searching for the maximum of any eigenvalue is feasible, because (a) the searching space within the class GD∗(n1,n2,…,nD+1) is much smaller than within all graphs with N nodes and diameter D; (b) we reduce the calculation of the Laplacian spectrum from a N×N to a (D+1)×(D+1) matrix.The maximum of any Laplacian eigenvalue obtained either theoretically or by numerical searching is applied to (1) investigate the topological features of graphs that maximize different Laplacian eigenvalues; (2) study the correlation between the maximum algebraic connectivity amax(N,D) and N as well as D and (3) evaluate two upper bounds of the algebraic connectivity that are proposed in the literature