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 . {1, 2, . 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.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Tilburg University, Center for Economic Research in its series Discussion Paper with number
102.