publication . Preprint . 2011

Diameters of Graphs with Spectral Radius at most $3/2\sqrt{2}$

Lan, Jingfen; Lu, Linyuan;
Open Access English
  • Published: 21 Dec 2011
Abstract
The spectral radius $\rho(G)$ of a graph $G$ is the largest eigenvalue of its adjacency matrix. Woo and Neumaier discovered that a connected graph $G$ with $\rho(G)\leq 3/2{\sqrt{2}}$ is either a dagger, an open quipu, or a closed quipu. The reverse statement is not true. Many open quipus and closed quipus have spectral radius greater than $3/2{\sqrt{2}}$. In this paper we proved the following results. For any open quipu $G$ on $n$ vertices ($n\geq 6$) with spectral radius less than $3/2{\sqrt{2}}$, its diameter $D(G)$ satisfies $D(G)\geq (2n-4)/3$. This bound is tight. For any closed quipu $G$ on $n$ vertices ($n\geq 13$) with spectral radius less than $3/2{\sq...
Subjects
free text keywords: Mathematics - Combinatorics, 05C50, 05C35
Related Organizations
Funded by
NSF| Extremal and Probabilistic Combinatorics II
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1000475
  • Funding stream: Directorate for Mathematical & Physical Sciences | Division of Mathematical Sciences
Download from

[1] A. E. Brouwer and A. Neumaier, The graphs with spectral radius between 2 and p2 + √5, Linear Algebra Appl. 115 (1989) 273-276. [OpenAIRE]

[2] S. M. Cioabaˇ, E. R. van Dam, J. H. Koolen, and J. Lee, Asymptotic results on the spectral radius and the diameter of graphs, Linear Algebra Appl. 432 (2010) 722-737.

[3] E. R. van Dam and R. E. Kooij, The minimal spectral radius of graphs with a given diameter, Linear Algebra Appl. 423 (2007) 408-419.

[4] D. M. Cvetkovi´c, M. Doob, and I. Gutman, On graphs whose spectral radius does not exceed (2 + √5)1/2, Ars Combin. 14 (1982) 225-239.

[5] X. Yuan, J. Shao and Y. Liu, The minimal spectral radius of graphs of order n with diameter n − 4, Linear Algebra Appl. 428 (2008) 2840-2851.

[6] D. M. Cvetkovi´c, M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, 15th ed, NewYork: Academic Press, 1980.

[7] A. J. Hoffman and J. H. Smith, On the spectral radii of topologically equivalent graphs, in: Fiedler (Ed.), Recent Advances in Graph Theory, Academia Praha, New York. (1975) 273-281.

[8] A. Hoffman, On limit points of spectral radii of non-negative symmetrical integral matrices, pp. 165 - 172 in: Lecture Notes in Math. 303, Springer, Berlin 1972.

[9] B. N. Parlett, The Symmetric Eigenvalue Problems, Prentice-Hall, Englewood Cliffs, NJ, 1980.

[10] A. J. Schwenk, Computing the characteristic polynomial of a graph, in: Graphs and Combinatorics, Lect. Notes in Math., vol. 406 (1974) 153-172.

[11] J. H. Smith, Some properties of the spectrum of a graph, 1970 Combinatorial Structures and their Applications, pp. 403-406, Gordan and Breach, New York.

[12] J. Lan, L. Lu, and L. Shi, Graphs with Diameter n − e Minimizing the Spectral Radius, submitted, http://arxiv.org/abs/1110.2444.

[13] X. Sun, Sorting graphs with with given diameter by spectral radius, Master Thesis, Tsinghua University, 2008 (in Chinese).

[14] J. Wang, Q. Huang, X. An, and F. Belardo, Some notes on graphs whose spectral radius is close to 23 √2, Linear Algebra Appl. 429 (2008) 1606-1618.

[15] R. Woo and A. Neumaier, On graphs whose spectral radius is bounded by 23 √2, Graphs Combin. 23 (2007) 713-726.

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue