Title | ||
---|---|---|
An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with its Laplacian |
Abstract | ||
---|---|---|
The authors give a new upper bound for the diameter $D(G)$ of a graph $G$ in terms of the eigenvalue of the Laplacian of $G$. The bound is $$ D(G)\leqq \lfloor\fract{cosh^{-1}(n-1)}{cosh^{-1}\frac{\lambda_n + \lambda_2}{\lambda_n - \lambda_2}}\rfloor +1, $$ where $0\leq \lambda_2 \leq \cdots \leq \lambda_n$ are the eigenvalues of the Laplacian of $G$ and where $\lfloor \rfloor$ is the floor function. |
Year | DOI | Venue |
---|---|---|
1994 | 10.1137/S0895480191217776 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
eigenvmues,floor function,diameter,eigenvalues associated,upper bound,laplacian,eigenvalues | Graph,Discrete mathematics,Combinatorics,Upper and lower bounds,Eigenvalues and eigenvectors,Mathematics,Lambda,Laplace operator | Journal |
Volume | Issue | ISSN |
7 | 3 | 0895-4801 |
Citations | PageRank | References |
32 | 4.24 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Fan R. K. Chung | 1 | 1171 | 255.25 |
V. Faber | 2 | 32 | 4.24 |
Thomas A. Manteuffel | 3 | 349 | 53.64 |