Print Email Facebook Twitter Graphs with given diameter maximizing the algebraic connectivity Title Graphs with given diameter maximizing the algebraic connectivity Author Wang, H. Kooij, R.E. Van Mieghem, P. Faculty Electrical Engineering, Mathematics and Computer Science Department Network Architectures & Services (NAS) Date 2010-06-30 Abstract We propose a class of graphs G?D(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 G?D(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. Subject graphsalgebraic connectivitymaximizediameter To reference this document use: http://resolver.tudelft.nl/uuid:cb32eba2-0207-4ea2-855c-2047fd8fbaaa DOI https://doi.org/10.1016/j.laa.2010.06.051 Publisher Elsevier ISBN 0024-3795 Source Linear Algebra and its Applications, Vol. 433, No. 11, June 2010; pre-print version Part of collection Institutional Repository Document type journal article Rights (c) 2010 Wang, H.Kooij, R.E.Van Mieghem, P. Files PDF Algebraicconnectivity.pdf 610.15 KB Close viewer /islandora/object/uuid%3Acb32eba2-0207-4ea2-855c-2047fd8fbaaa/datastream/OBJ/view