The Minimal Spectral Radius of Graphs with a Given Diameter
The Minimal Spectral Radius of Graphs with a Given Diameter
复制标题
DOI：
10.2139/ssrn.945575
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
E. V. van Dam;R. Kooij
中科院分区：
文献类型：
--
作者：
E. V. van Dam;R. Kooij
图的谱半径（即，其对应邻接矩阵的最大特征值）在网络中病毒传播的建模中起着重要作用。事实上，光谱半径越小，网络对病毒传播的鲁棒性就越大。在n个结点上的所有连通图中，路Pn具有最小的谱半径。然而，其直径D，即，图中任何一对节点之间的最大跳数是最大可能的，即D = n - 1。通常，通信网络被设计成使得直径小，因为在连接上穿过的节点的数量越大，在网络上运行的服务的质量越低。这导致我们陈述以下问题：在n个节点和给定的直径D上，哪个连通图具有最小谱半径？本文对直径为D ∈ fenced（1，2，n = fenced（frac（n，2）），n - 3，n - 2，n - 1）的图，显式地解决了这个问题.此外，我们解决了几乎所有的图上最多20个节点的计算机搜索的问题。© 2007 Elsevier Inc. All rights reserved.
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.