From local adjacency polynomials to locally pseudo-distance-regular graphs
type: Item
instance of: scholarly article
title: From local adjacency polynomials to locally pseudo-distance-regular graphs
zbMATH Open document ID: 0888.05056
author: E. Garriga
author: Miquel Angel Fiol
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-09-15T00:00:00Z
review text: The local adjacency polynomials can be thought of as a generalization, for all graphs, of (the sums of) the distance polynomials of distance-regular graphs. The term ``local'' here means that we ``see'' the graph from a given vertex, and it is the price we must pay for speaking of a kind of distance-regularity when the graph is not regular. It is shown that when the value at \(\lambda\) (the maximum eigenvalue of the graph) of the local adjacency polynomials is large enough, then the eccentricity of the base vertex tends to be small. Moreover, when such a vertex is ``tight'' (that is, the value of a certain polynomial just fails to satisfy the condition) and fulfils certain additional extremality conditions, then all the polynomials attain their maximum possible values at \(\lambda\), and the graph turns out to be pseudo-distance-regular around the vertex. As a consequence of the above results, some new characterizations of distance-regular graphs are derived. For example, it is shown that a regular graph \(\Gamma\) with \(d+1\) distinct eigenvalues is distance-regular if, and only if, the number of vertices at distance \(d\) from any given vertex is the value at \(\lambda\) of the highest degree member of an orthogonal system of polynomials, which depends only on the spectrum of the graph.
Mathematics Subject Classification ID: 05E25
Mathematics Subject Classification ID: 05E20
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1060744
zbMATH Keywords: local adjacency polynomials
zbMATH Keywords: distance polynomials
zbMATH Keywords: distance-regular graphs
zbMATH Keywords: eigenvalue
zbMATH Keywords: eccentricity
zbMATH Keywords: pseudo-distance-regular
zbMATH Keywords: regular graph
zbMATH Keywords: orthogonal system of polynomials
zbMATH Keywords: spectrum
MaRDI profile type: Publication
full work available at URL: jctb.1997.1778
OpenAlex ID: W1987779054
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: Girth, valency, and excess
cites work: Q4770409
cites work: Diameters and Eigenvalues
cites work: An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian
cites work: Q3992965
cites work: Developments in the theory of graph spectra
cites work: Q3907599
cites work: Eigenvalues and the diameter of graphs
cites work: A characterization of distance-regular graphs with diameter three
cites work: Distance biregular bipartite graphs
cites work: Diameter, covering index, covering radius and eigenvalues
cites work: Eigenvalues, eigenspaces and distances to subsets
cites work: The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs
cites work: On a class of polynomials and its relation with the spectra and diameters of graphs
cites work: From regular boundary graphs to antipodal distance-regular graphs
cites work: Locally pseudo-distance-regular graphs
cites work: Problems in algebraic combinatorics
cites work: Feasibility conditions for the existence of walk-regular graphs
cites work: Distance-regularised graphs are distance-regular or distance-biregular
cites work: Distance-regularity and the spectrum of graphs
cites work: On the Polynomial of a Graph
cites work: Isoperimetric Inequalities and Eigenvalues
cites work: Eigenvalues, diameter, and mean distance in graphs
cites work: Spectral diameter estimates for \(k\)-regular graphs
cites work: Q3997785
cites work: Q3999365
DOI: 10.1006/JCTB.1997.1778
description: scientific article; zbMATH DE number 1060744