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

Recently, in the study of the properties of a graph which are revealed by its spectrum, an upper bound for the diameter in terms of the so-called alternating polynomial and the square norm of the positive eigenvector has been given. For a regular graph, this result can also be thought of as a lower bound on its number of vertices in terms of its distinct eigenvalues and its diameter. The aim of this paper is to study the structure of the graphs realizing their bound, which are called boundary graphs. Special attention is paid to boundary graphs with spectrally maximum diameter (that is, the number of distinct eigenvalues minus one). These graphs include all 2-antipodal distance-regular graphs. For smaller diameters, boundary graphs seem to bear a much more involved structure and some constructions are presented. The importance of some distinguished vertices, called conjugate, shows to be crucial to analyze the whole structure of the graphs under consideration.