Graphs with given diameter maximizing the algebraic connectivity
article
We propose a class of graphs GD(n<sub>1</sub>,n<sub>2</sub>,⋯,n <sub>D+1</sub>), containing of a chain of D+1 cliques K n<sub>1</sub>,K n <sub>2</sub>,⋯,Kn<sub>D+1</sub>, where neighboring cliques are fully-interconnected. The class of graphs has diameter D and size N=∑<sub>1≤i≤D+1</sub>n<sub>i</sub>. 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(n<sub>1</sub>,n<sub>2</sub>,⋯,n <sub>D+1</sub>) 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. © 2010 Elsevier Inc. All rights reserved.
Topics
TNO Identifier
409815
Source
Linear Algebra and Its Applications, 433(11-12), pp. 1889-1908.
Pages
1889-1908
Files
To receive the publication files, please send an e-mail request to TNO Repository.