zbMATH — the first resource for mathematics

Locally pseudo-distance-regular graphs. (English) Zbl 0861.05064
The concept of local pseudo-distance-regularity, introduced in this paper, can be thought of as a natural generalization of distance-regularity for non-regular graphs. Intuitively speaking, such a concept is related to the regularity of graph $$\Gamma$$ when it is seen from a given vertex. The price to be paid for speaking about a kind of distance-regularity in the non-regular case seems to be locality. Thus, we find out that there are no genuine “global” pseudo-distance-regular graphs: when pseudo-distance-regularity is shared by all the vertices, the graph turns out to be distance-regular. Our main result is a characterization of locally pseudo-distance-regular graphs, in terms of the existence of the highest-degree member of a sequence of orthogonal polynomials. As a particular case, we obtain the following new characterization of distance-regular graphs: A graph $$\Gamma$$, with adjacency matrix $${\mathbf A}$$, is distance-regular if and only if $$\Gamma$$ has spectrally maximum diameter $$D$$, all its vertices have eccentricity $$D$$, and the distance matrix $${\mathbf A}_D$$ is a polynomial of degree $$D$$ in $${\mathbf A}$$.

MSC:
 5e+30 Association schemes, strongly regular graphs 5e+35 Orthogonal polynomials (combinatorics) (MSC2000)
Full Text: