×

On the spectrum, the growth, and the diameter of a graph. (English) Zbl 0930.05066

A lower bound is given for the harmonic mean of the growth in a finite undirected graph \(\Gamma\) in terms of the eigenvalues of the Laplacian of \(\Gamma\). For a connected graph, this bound is tight if and only if the graph is distance-regular. Bounds on the diameter of a “sphere-regular” graph follow. Finally, a lower bound is given for the growth in an infinite undirected graph of bounded degree in terms of the spectrum of its Laplacian. \(\copyright\) Academic Press.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C12 Distance in graphs
05E30 Association schemes, strongly regular graphs
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alon, N.; Milman, V. D., \(λ_1\), J. Combin. Theory Ser. B, 38, 73-88 (1985) · Zbl 0549.05051
[2] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin · Zbl 0747.05073
[3] Biggs, N., Algebraic Graph Theory (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge
[4] Chung, F. R.K.; Faber, V.; Manteuffel, T. H., An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian, SIAM J. Discrete Math., 7, 443-457 (1994) · Zbl 0808.05072
[5] Chung, F. R.K., Diameters and eigenvalues, J. Amer. Math. Soc., 2, 187-196 (1989) · Zbl 0678.05037
[6] Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36 (1963) · Zbl 0112.14901
[7] Gerl, P.; Woess, W., Simple random walks on trees, European J. Combin., 7, 321-331 (1986) · Zbl 0606.05021
[8] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 261-277 (1988) · Zbl 0661.05035
[9] Mohar, B.; Woess, W., A survey on spectra of infinite graphs, Bull. London Math. Soc., 21, 209-234 (1989) · Zbl 0645.05048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.