Asymptotic results on the spectral radius and the diameter of graphs

被引：18

作者：

Cioaba, Sebastian M. ^{[2
]}

van Dam, Edwin R. ^{[1
]}

Koolen, Jack H. ^{[3
]}

Lee, Jae-Ho ^{[4
]}

机构：

[1] Tilburg Univ, Dept Econometr & OR, NL-5000 LE Tilburg, Netherlands

[2] Univ Delaware, Dept Math Sci, Newark, DE 19716 USA

[3] Pohang Univ Sci & Technol, Dept Math, Pohang 790784, South Korea

[4] Univ Wisconsin, Dept Math, Madison, WI 53706 USA

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2010年 / 432卷 / 2-3期

关键词：

Graphs; Spectral radius; Diameter; Limit points; Quipus; root 2+root 5; 3/2; root; 2;

D O I：

10.1016/j.laa.2009.09.016

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study graphs with spectral radius at most 3/2 root 2 and refine results by Woo and Neumaier [R. Woo, A. Neumaier, On graphs whose spectral radius is bounded by 3/2 root 2, Graphs Combin. 23 (2007) 713-726]. We study the limit points of the spectral radii of certain families of graphs, and apply the results to the problem of minimizing the spectral radius among the graphs with a given number of vertices and diameter. In particular, we consider the cases when the diameter is about half the number of vertices, and when the diameter is near the number of vertices. We prove certain instances of a conjecture posed by Van Dam and Kooij [E.R. Van Dam, R.E. Kooij, The minimal spectral radius of graphs with a given diameter, Linear Algebra Appl. 423 (2007) 408-419] and show that the conjecture is false for the other instances. (C) 2009 Elsevier Inc. All rights reserved.

引用

页码：722 / 737

页数：16

共 13 条

[1]

[Anonymous], 1997, Eigenspaces of graphs

[2]

Brouwer A.E., 1989, Distance-Regular Graphs

[3] THE GRAPHS WITH SPECTRAL-RADIUS BETWEEN 2 AND 2 SQUARE-ROOT+5 SQUARE-ROOT [J].

BROUWER, AE ;

NEUMAIER, A .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1989, 114 :273-276

[4]

Cvetkovic D. M., 1980, Spectra of graphs

[5] On bags and bugs [J].

Hansen, Pierre ;

Stevanovic, Dragan .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (07) :986-997

[6]

Hoffman A.J., 1975, RECENT ADV GRAPH THE, P273

[7]

Hoffman A.J., 1972, Lecture Notes Math., V303, P165

[8]

Smith J.H., 1970, COMBINATORIAL STRUCT, P403

[9] Graphs with given diameter maximizing the spectral radius [J].

van Dam, E. R. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 426 (2-3) :454-457

[10] The minimal spectral radius of graphs with a given diameter [J].

van Dam, E. R. ;

Kooij, R. E. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (2-3) :408-419

← 1 2 →