Name
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 Γ 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 λ of the highest degree member of an orthogonal system of polynomials, which depend only on the spectrum of the graph. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1006/jctb.1997.1778 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
local adjacency polynomial,pseudo-distance-regular graph,spectrum,distance regular graph,eigenvalues,satisfiability | Adjacency list,Discrete mathematics,Strongly regular graph,Circulant graph,Combinatorics,Graph energy,Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Regular graph,Mathematics | Journal |
Volume | Issue | ISSN |
71 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
28 | 2.88 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. A. Fiol | 1 | 816 | 87.28 |
| E. Garriga | 2 | 164 | 19.92 |