Article ID Journal Published Year Pages File Type
4655532 Journal of Combinatorial Theory, Series A 2013 6 Pages PDF
Abstract

The spectral excess theorem for distance-regular graphs states that a regular (connected) graph is distance-regular if and only if its spectral excess equals its average excess. Recently, some local as well as global approaches to this result have been used to obtain new versions of the theorem for nonregular graphs, and also to study the problem of characterizing those graphs which have the corresponding distance-regularity property. In this paper such approaches are compared and related. In particular, a recent inequality of Lee and Weng for nonregular graphs, which is similar to the one that leads to the spectral excess theorem, is improved. As a consequence, we obtain new characterizations of some properties related to that of distance-regularity. For instance, a sufficient condition for to be distance-polynomial is obtained.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics