# Graphs with given diameter maximizing the algebraic connectivity

Graphs with given diameter maximizing the algebraic connectivity

Wang, H.

Kooij, R.E.

van Mieghem, P.

TNO Informatie- en Communicatietechnologie

We propose a class of graphs GD(n_{1},n_{2},⋯,n _{D+1}), containing of a chain of D+1 cliques K n_{1},K n _{2},⋯,Kn_{D+1}, where neighboring cliques are fully-interconnected. The class of graphs has diameter D and size N=∑_{1≤i≤D+1}n_{i}. 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_{1},n_{2},⋯,n _{D+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. © 2010 Elsevier Inc. All rights reserved.

Image processing

Algebraic connectivity

Diameter

Graphs

Maximize

Graphs

Hopcount

matrix

Searching spaces

Upper Bound

Algebra

Eigenvalues and eigenfunctions

Laplace transforms

Topology

http://resolver.tudelft.nl/uuid:f2116ebf-d0a0-4024-b6bb-1e985c36eb3c

DOI TNO identifier409815

Linear Algebra and Its Applications, 433 (11-12), 1889-1908

Document typearticle

To receive the publication files, please send an e-mail request to TNO Library. |