From local adjacency polynomials to locally pseudo-distance-regular graphs. (English) Zbl 0888.05056

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.


05E25 Group actions on posets, etc. (MSC2000)
05E20 Group actions on designs, etc. (MSC2000)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI


[1] Alon, N.; Milman, V.D., λ1, J. combin. theory ser. B, 38, 73-88, (1985) · Zbl 0549.05051
[2] Biggs, N., Girth, valency and excess, Linear algebra appl., 31, 55-59, (1980) · Zbl 0442.05037
[3] Biggs, N., Algebraic graph theory, (1974), Cambridge Univ. Press Cambridge · Zbl 0284.05101
[4] Chung, F.R.K., Diameter and eigenvalues, J. amer. math. soc., 2, 187-196, (1989) · Zbl 0678.05037
[5] Chung, F.R.K.; Faber, V.; Manteuffel, T.A., An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian, SIAM J. discrete math., 7, 443-457, (1994) · Zbl 0808.05072
[6] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer-Verlag Berlin · Zbl 0747.05073
[7] Cvetkovic, D.M.; Doob, M., Developments in the theory of graph spectra, Linear and multilinear algebra, 18, 153-181, (1985) · Zbl 0615.05039
[8] Cvetkovic, D.M.; Doob, M.; Sachs, H., Spectra of graphs—theory and applications, (1980), Deutscher Verlag der Wissenschaften Berlin · Zbl 0458.05042
[9] van Dam, E.R.; Haemers, W.H., Eigenvalues and the diameter of graphs, Linear and multilinear algebra, 39, 33-44, (1995) · Zbl 0831.05046
[10] E. R. van Dam, W. H. Haemers, A characterization of distance-regular graphs with diameter three, J. Algebraic Combin. · Zbl 0874.05060
[11] Delorme, C., Distance biregular bipartite graphs, Europ. J. combin., 15, 223-238, (1994) · Zbl 0804.05031
[12] Delorme, C.; Solé, P., Diameter, covering index, covering radius and eigenvalues, Europ. J. combin., 12, 95-108, (1991) · Zbl 0737.05067
[13] Delorme, C.; Tillich, J.P., Eigenvalues, eigenspaces and distances to subsets, Discrete math., 165/166, 161-184, (1997) · Zbl 0881.05087
[14] M. A. Fiol, E. Garriga, The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs · Zbl 0914.05050
[15] Fiol, M.A.; Garriga, E.; Yebra, J.L.A., On a class of poilynomials and its relation with the spectra and diameter of graphs, J. combin. theory ser. B, 67, 48-61, (1996) · Zbl 0857.05101
[16] M. A. Fiol, E. Garriga, J. L. A. Yebra, From regular boundary graphs to antipodal distance-regular graphs · Zbl 0927.05086
[17] Fiol, M.A.; Garriga, E.; Yebra, J.L.A., Locally pseudo-distance-regular graphs, J. combin. theory ser. B, 68, 179-205, (1996) · Zbl 0861.05064
[18] Godsil, C.D., Algebraic combinatorics, (1993), Chapman & Hall London/new York · Zbl 0814.05075
[19] Godsil, C.D.; McKay, B.D., Feasibility conditions forthe existence of walk-regular graphs, Linear algebra appl., 30, 51-61, (1980) · Zbl 0452.05045
[20] Godsil, C.D.; Shawe-Taylor, J., Distance-regularised graphs are distance-regular or distance-biregular, J. combin. theory ser. B, 43, 14-24, (1987) · Zbl 0616.05041
[21] Haemers, W.H., Distance-regularity and the spectrum of graphs, Linear algebra appl., 236, 265-278, (1996) · Zbl 0845.05101
[22] Hoffman, A.J., On the polynomial of a graph, Amer. math. monthly, 70, 30-36, (1963) · Zbl 0112.14901
[23] Kahale, N., Isoperimetric inequalities and eigenvalues, SIAM J. discrete math., 10, 30-40, (1997) · Zbl 0917.05039
[24] Mohar, B., Eigenvalues, diameter and Mean distance in graphs, Graphs combin., 7, 53-64, (1991) · Zbl 0771.05063
[25] Quenell, G., Spectral diameter estimates fork, Adv. math., 106, 122-148, (1994) · Zbl 0808.05071
[26] Nikiforov, A.F.; Suslov, S.K.; Uvarov, V.B., Classical orthogonal polynomials of a discrete variable, (1991), Springer-Verlag Berlin · Zbl 0743.33001
[27] Sarnak, P.C., Some applications of modular forms, (1990), Cambridge Univ. Press Cambridge · Zbl 0721.11015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.