%0 Journal Article %1 Fiol97 %A Fiol, Miguel Àngel %A Carriga, E. %D 1997 %J Journal of Combinatorial Theory, Series B %K distance-regular graph.theory polynomial predistance %N 2 %P 162 - 183 %R 10.1006/jctb.1997.1778 %T From Local Adjacency Polynomials to Locally Pseudo-Distance-Regular Graphs %V 71 %X 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λ(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λ, 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Γwithd+1 distinct eigenvalues is distance-regular if, and only if, the number of vertices at distancedfrom any given vertex is the value atλof the highest degree member of an orthogonal system of polynomials, which depend only on the spectrum of the graph.

@article{Fiol97, abstract = {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λ(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λ, 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Γwithd+1 distinct eigenvalues is distance-regular if, and only if, the number of vertices at distancedfrom any given vertex is the value atλof the highest degree member of an orthogonal system of polynomials, which depend only on the spectrum of the graph. }, added-at = {2015-07-22T05:02:41.000+0200}, author = {Fiol, Miguel \`{A}ngel and Carriga, E.}, biburl = {https://www.bibsonomy.org/bibtex/2ffe539cfce2bded384949f1a94a4a344/ytyoun}, doi = {10.1006/jctb.1997.1778}, interhash = {da69b9be849b59675f0cf535aca6cf0f}, intrahash = {ffe539cfce2bded384949f1a94a4a344}, issn = {0095-8956}, journal = {Journal of Combinatorial Theory, Series B }, keywords = {distance-regular graph.theory polynomial predistance}, number = 2, pages = {162 - 183}, timestamp = {2015-07-22T05:02:41.000+0200}, title = {From Local Adjacency Polynomials to Locally Pseudo-Distance-Regular Graphs }, volume = 71, year = 1997 }