Some applications of the proper and adjacency polynomials in the theory of graph spectra
type: Item
instance of: scholarly article
title: Some applications of the proper and adjacency polynomials in the theory of graph spectra
zbMATH Open document ID: 0885.05084
author: J. Ning
published in: The Electronic Journal of Combinatorics
publication date: 1998-02-12T00:00:00Z
full work available at URL: https://eudml.org/doc/119259
full work available at URL: v4i1r21.html
review text: Summary: Given a vertex \(u\in V\) of a graph \(\Gamma=(V,E)\), the (local) proper polynomials constitute a sequence of orthogonal polynomials, constructed from the so-called \(u\)-local spectrum of \(\Gamma\). These polynomials can be thought of as a generalization, for all graphs, of the distance polynomials for the distance-regular graphs. The (local) adjacency polynomials, which are basically sums of proper polynomials, were recently used to study a new concept of distance-regularity for non-regular graphs, and also to give bounds on some distance-related parameters such as the diameter. Here we develop the subject of these polynomials and give a survey of some known results involving them. For instance, distance-regular graphs are characterized from the spectrum and the number of vertices at ``extremal distance'' from each of their vertices. Afterwards, some new applications of both, the proper and adjacency polynomials, are derived, such as bounds for the radius of \(\Gamma\) and the weight \(k\)-excess of a vertex. Given the integers \(k,\mu\geq 0\), let \(\Gamma_k^\mu(u)\) denote the set of vertices which are at distance at least \(k\) from a vertex \(u\in V\), and there exist exactly \(\mu\) (shortest) \(k\)-paths from \(u\) to each such vertex. As a main result, an upper bound for the cardinality of \(\Gamma_k^\mu(u)\) is derived, showing that \(|\Gamma_k^\mu(u)|\) decreases at least as \(O(\mu^{-2})\), and the cases in which the bound is attained are characterized. When these results are particularized to regular graphs with four distinct eigenvalues, we reobtain a result of Van Dam about 3-class association schemes, and prove some conjectures of Haemers and Van Dam, about the number of vertices at distance three from every vertex of a regular graph with four distinct eigenvalues---setting \(k=2\) and \(\mu=0\)---and, more generally, the number of non-adjacent vertices to every vertex \(u\in V\), which have \(\mu\) common neighbours with it.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05E30
Mathematics Subject Classification ID: 05E35
zbMATH DE Number: 1118006
zbMATH Keywords: orthogonal polynomials
zbMATH Keywords: spectrum
zbMATH Keywords: distance polynomials
zbMATH Keywords: distance-regular graphs
zbMATH Keywords: eigenvalues
zbMATH Keywords: association schemes
zbMATH Keywords: distance
zbMATH Keywords: regular graph
MaRDI profile type: Publication
Recommended article: Q4820551
Recommended article: The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs
Recommended article: On a class of polynomials and its relation with the spectra and diameters of graphs
Recommended article: Applications of Pólya's theorem to some classes of graphs
Recommended article: Lexicographic polynomials of graphs and their spectra
Recommended article: The alternating polynomials and their relation with the spectra and conditional diameters of graphs
Recommended article: A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
Recommended article: Spectra of regular graphs and hypergraphs and orthogonal polynomials
Recommended article: Q4687753
Recommended article: Q4590674
description: scientific article; zbMATH DE number 1118006