An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian

DOI10.1137/S0895480191217776zbMath0808.05072MaRDI QIDQ4307051

Vance Faber, Fan R. K. Chung, Thomas A. Manteuffel

Publication date: 7 March 1995

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

upper boundeigenvaluesdiameterLaplacian

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (27)

On the Laplacian Eigenvalues and Metric Parameters of Hypergraphs ⋮ Cutoff on graphs and the Sarnak-Xue density of eigenvalues ⋮ The alternating polynomials and their relation with the spectra and conditional diameters of graphs ⋮ Eigenvalues, eigenspaces and distances to subsets ⋮ Laplacian spectral bounds for clique and independence numbers of graphs ⋮ Cutoff on all Ramanujan graphs ⋮ From local adjacency polynomials to locally pseudo-distance-regular graphs ⋮ A computational attack on the conjectures of Graffiti: New counterexamples and proofs ⋮ Old and new results on algebraic connectivity of graphs ⋮ Boundary graphs. II: The limit case of a spectral property ⋮ Graphs with given diameter maximizing the algebraic connectivity ⋮ On the covering radius of an unrestricted code as a function of the rate and dual distance ⋮ Bounds on special subsets in graphs, eigenvalues and association schemes ⋮ Gelfand's inverse problem for the graph Laplacian ⋮ Inverse Problems for Discrete Heat Equations and Random Walks for a Class of Graphs ⋮ The spectra of Manhattan street networks ⋮ On Rayleigh-Ritz ratios of a generalized Laplacian matrix of directed graphs ⋮ Bounding the gap between extremal Laplacian eigenvalues of graphs ⋮ The Laplacian spectral radius of a graph under perturbation ⋮ The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs ⋮ Multidiameters and multiplicities ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ Bounding the diameter and the mean distance of a graph from its eigenvalues: Laplacian versus adjacency matrix methods ⋮ An eigenvalue bound for the Laplacian of a graph ⋮ On the spectrum, the growth, and the diameter of a graph ⋮ Laplacian matrices of graphs: A survey ⋮ Loose laplacian spectra of random hypergraphs

This page was built for publication: An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian