AN UPPER BOUND ON THE DIAMETER OF A GRAPH FROM EIGENVALUES ASSOCIATED WITH ITS LAPLACIAN

被引：57

作者：

CHUNG, FRK ^{[1
]}

FABER, V ^{[1
]}

MANTEUFFEL, TA ^{[1
]}

机构：

[1] LOS ALAMOS NATL LAB,LOS ALAMOS,NM 87545

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1994年 / 7卷 / 03期

关键词：

LAPLACIAN; DIAMETER; EIGENVALUES;

D O I：

10.1137/S0895480191217776

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The authors give a new upper bound for the diameter D(G) of a graph G in terms of the eigenvalues of the Laplacian of G. The bound is D(G) less-than-or-equal-to [cosh-1 (n - 1)/cosh-1 (lambda(n) + lambda2/lambda(n) - lambda2)] + 1. where 0 less-than-or-equal-to lambda2 less-than-or-equal-to ... less-than-or-equal-to lambda(n) are the eigenvalues of the Laplacian of G and where [] is the floor function.

引用

页码：443 / 457

页数：15

共 17 条

[1] LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS [J].