The minimal spectral radius of graphs with a given diameter

被引:54
作者
van Dam, E. R.
Kooij, R. E.
机构
[1] Tilburg Univ, Dept Econometr & OR, NL-5000 LE Tilburg, Netherlands
[2] Delft Univ Technol, Fac Elect Engn Math & Comp Sci, NL-2600 GA Delft, Netherlands
[3] TNO ICT, NL-2600 GB Delft, Netherlands
关键词
graphs; spectral radius; diameter; networks; virus propagation;
D O I
10.1016/j.laa.2007.01.011
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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 P-n 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 is an element of {1, 2, [n/2], n - 3, 2, n - 1}. Moreover, we solve the problem for almost all graphs on at most 20 nodes by a computer search. (C) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码:408 / 419
页数:12
相关论文
共 50 条
[41]   Y The Minimal Spectral Radius with Given Independence Number [J].
Choi, Jinwon ;
Park, Jooyeon .
RESULTS IN MATHEMATICS, 2024, 79 (02)
[42]   On the Laplacian Spectral Radius of Unicyclic Graphs with Fixed Diameter [J].
Guo, Shu-Guang .
ARS COMBINATORIA, 2012, 106 :47-58
[43]   Tree with minimal Laplacian spectral radius and diameter n-4 [J].
Liu, Ruifang ;
Jia, Huicai ;
Yuan, Jinjiang .
ARS COMBINATORIA, 2013, 109 :345-352
[44]   Maximizing the Laplacian spectral radii of graphs with given diameter [J].
Zhai, Mingqing ;
Shu, Jinlong ;
Lu, Zhonghua .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2009, 430 (8-9) :1897-1905
[45]   Variable neighbourhood search for connected graphs of fixed order and size with minimal spectral radius [J].
Kostic, Kristina ;
Drazic, Zorica ;
Savic, Aleksandar ;
Stanic, Zoran .
KUWAIT JOURNAL OF SCIENCE, 2024, 51 (01)
[46]   ON RADIUS AND TYPICAL PROPERTIES OF n-VERTEX GRAPHS OF GIVEN DIAMETER [J].
Fedoryaeva, T., I .
SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2021, 18 :345-357
[47]   The maximal (signless Laplacian) spectral radius of connected graphs with given matching number [J].
Chen, Xiaodan ;
Lu, Fuliang .
ARS COMBINATORIA, 2016, 126 :237-247
[48]   The bounds of spectral radius of graphs with a given size of independent set [J].
Tan Xuezhong ;
Liu, Bolian .
ARS COMBINATORIA, 2008, 88 :97-107
[49]   The maximum spectral radius of graphs of given size with forbidden subgraph [J].
Fang, Xiaona ;
You, Lihua .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2023, 666 :114-128
[50]   Maximization of the spectral radius of block graphs with a given dissociation number [J].
Das, Joyentanuj ;
Mohanty, Sumit .
APPLIED MATHEMATICS AND COMPUTATION, 2024, 465