Locally pseudo-distance-regular graphs
type: Item
instance of: scholarly article
title: Locally pseudo-distance-regular graphs
zbMATH Open document ID: 0861.05064
author: E. Garriga
author: Miquel Angel Fiol
author: J. Luis A. Yebra
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-05-19T00:00:00Z
review text: 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}\).
Mathematics Subject Classification ID: 05E30
Mathematics Subject Classification ID: 05E35
zbMATH DE Number: 954822
zbMATH Keywords: local pseudo-distance-regularity
zbMATH Keywords: pseudo-distance-regular graphs
zbMATH Keywords: orthogonal polynomials
zbMATH Keywords: distance-regular graphs
MaRDI profile type: Publication
full work available at URL: jctb.1996.0063
OpenAlex ID: W2045020235
DOI: 10.1006/JCTB.1996.0063
description: scientific article; zbMATH DE number 954822