Name
Abstract | ||
|---|---|---|
Recently, several results bounding the diameter of a regular graph from its eigenvalues have been presented. They admit the following unified presentation: Let λ 0 > λ 1 > … > λ d be the d + 1 distinct eigenvalues of a graph of order n and diameter D , and let P be a polynomial. Then, P ( λ 0 ) > ‖ P ‖ ∞ ( n −1) ⇒ D ⩽ dgr P , where where ‖ P ‖ ∞ = max 1 ⩽ i ⩽ d {| P ( λ i )|}. The best results are obtained when P = P k is the so-called k -alternating polynomial of degree k . For not necessarily regular graphs the above condition reads P k ( λ 0 ) > ‖ P k ‖ ∞ (‖ v ‖ 2 − 1) ⇒ D ⩽ k , where v is the positive eigenvector with smallest component equal to 1. To measure the accuracy of this result it seems interesting to investigate the graphs for which P k ( λ 0 ) = ‖ P k ‖ ∞ (‖ v ‖ 2 − 1), that we call boundary graphs. This has already been done for k = d − 1, and is undertaken in this paper for 1 ⩽ k < d − 1. We present several families of such graphs, paying special attention to graphs with diameter D = k + 1. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0012-365X(97)00153-2 | Discrete Mathematics |
Keywords | DocType | Volume |
limit case,spectral property,boundary graph | Journal | 182 |
Issue | ISSN | Citations |
1-3 | Discrete Mathematics | 12 |
PageRank | References | Authors |
1.08 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. A. Fiol | 1 | 816 | 87.28 |
| E. Garriga | 2 | 164 | 19.92 |
| J. L.A. Yebra | 3 | 291 | 36.48 |