Boundary graphs — II The limit case of a spectral property Original Research Article

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‖∞ = max1 ⩽i⩽d {|P(λi)|}. The best results are obtained when P = Pk is the so-called k-alternating polynomial of degree k. For not necessarily regular graphs the above condition reads Pk(λ0) > ‖Pk‖∞(‖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 Pk(λ0) = ‖Pk‖∞(‖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.