The minimal spectral radius of graphs with a given diameter
article
The spectral radius of a graph (i.e., the largest eigenvalue of its corresponding adjacency matrix) plays an important role in modeling virus propagation in networks. In fact, the smaller the spectral radius, the larger the robustness of a network against the spread of viruses. Among all connected graphs on n nodes the path Pn has minimal spectral radius. However, its diameter D, i.e., the maximum number of hops between any pair of nodes in the graph, is the largest possible, namely D = n - 1. In general, communication networks are designed such that the diameter is small, because the larger the number of nodes traversed on a connection, the lower the quality of the service running over the network. This leads us to state the following problem: which connected graph on n nodes and a given diameter D has minimal spectral radius? In this paper we solve this problem explicitly for graphs with diameter D ∈ fenced(1, 2, ⌊⌋ fenced(frac(n, 2)), n - 3, n - 2, n - 1). Moreover, we solve the problem for almost all graphs on at most 20 nodes by a computer search. © 2007 Elsevier Inc. All rights reserved.
Topics
TNO Identifier
240001
Source
Linear Algebra and Its Applications, 423(2-3), pp. 408-419.
Pages
408-419
Files
To receive the publication files, please send an e-mail request to TNO Repository.