The spectral excess theorem for distance-regular graphs having distance-\(d\) graph with fewer distinct eigenvalues. (English) Zbl 1339.05090
Summary: Let \(\Gamma \) be a distance-regular graph with diameter \(d\) and Kneser graph \(K=\Gamma _d\), the distance-\(d\) graph of \(\Gamma \). We say that \(\Gamma \) is partially antipodal when \(K\) has fewer distinct eigenvalues than \(\Gamma \). In particular, this is the case of antipodal distance-regular graphs (\(K\) with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (\(K\) with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with \(d+1\) distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance \(d\) from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular.
Keywords:
distance-regular graph; Kneser graph; partial antipodality; spectrum; predistance polynomialsReferences:
| [1] | Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin, New York (1989) · Zbl 0747.05073 · doi:10.1007/978-3-642-74341-2 |
| [2] | Brouwer, A.E., Fiol, M.A.: Distance-regular graphs where the distance-\[d\] d graph has fewer distinct eigenvalues. Linear Algebra Appl. 480, 115-126 (2015) · Zbl 1314.05053 · doi:10.1016/j.laa.2015.04.020 |
| [3] | Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Springer, (2012). http://homepages.cwi.nl/ aeb/math/ipm/ · Zbl 1231.05001 |
| [4] | Cámara, M., Fàbrega, J., Fiol, M.A., Garriga, E.: Some families of orthogonal polynomials of a discrete variable and their applications to graphs and codes. Electron. J. Comb. 16(1), R83 (2009) · Zbl 1230.05120 |
| [5] | Dalfó, C., van Dam, E.R., Fiol, M.A., Garriga, E., Gorissen, B.L.: On almost distance-regular graphs. J. Comb. Theory Ser. A 118, 1094-1113 (2011) · Zbl 1225.05249 · doi:10.1016/j.jcta.2010.10.005 |
| [6] | Fiol, M.A.: An eigenvalue characterization of antipodal distance-regular graphs. Electron. J. Comb. 4, R30 (1997) · Zbl 0885.05082 |
| [7] | Fiol, M.A.: A quasi-spectral characterization of strongly distance-regular graphs. Electron. J. Comb. 7, R51 (2000) · Zbl 0956.05103 |
| [8] | Fiol, M.A.: Some spectral characterization of strongly distance-regular graphs. Comb. Probab. Comput. 10(2), 127-135 (2001) · Zbl 0973.05064 · doi:10.1017/S0963548301004564 |
| [9] | Fiol, M.A.: Algebraic characterizations of distance-regular graphs. Discret. Math. 246, 111-129 (2002) · Zbl 1025.05060 · doi:10.1016/S0012-365X(01)00255-2 |
| [10] | Fiol, M.A., Gago, S., Garriga, E.: A simple proof of the spectral excess theorem for distance-regular graphs. Linear Algebra Appl. 432, 2418-2422 (2010) · Zbl 1221.05112 · doi:10.1016/j.laa.2009.07.030 |
| [11] | Fiol, M.A., Garriga, E.: From local adjacency polynomials to locally pseudo-distance-regular graphs. J. Comb. Theory Ser. B 71, 162-183 (1997) · Zbl 0888.05056 · doi:10.1006/jctb.1997.1778 |
| [12] | Fiol, M.A., Garriga, E., Yebra, J.L.A.: Locally pseudo-distance-regular graphs. J. Comb. Theory Ser. B 68, 179-205 (1996) · Zbl 0861.05064 · doi:10.1006/jctb.1996.0063 |
| [13] | Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall, NewYork (1993) · Zbl 0784.05001 |
| [14] | Hoffman, A.J.: On the polynomial of a graph. Am. Math. Mon. 70, 30-36 (1963) · Zbl 0112.14901 · doi:10.2307/2312780 |
| [15] | Smith, D.H.: Primitive and imprimitive graphs. Q. J. Math. Oxf. 22(2), 551-557 (1971) · Zbl 0222.05111 · doi:10.1093/qmath/22.4.551 |
| [16] | van Dam, E.R.: The spectral excess theorem for distance-regular graphs: a global (over)view. Electron. J. Comb. 15(1), R129 (2008) · Zbl 1180.05130 |
| [17] | van Dam, E.R., Koolen, J.H., Tanaka, H.: Distance-regular graphs, preprint (2014). arXiv:1410.6294 [math.CO] · Zbl 1335.05062 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
